多组数据,A=B=0;每组测试数据,包含两个正整数A,B。对于每组测试数据,在第一行内输出一个整数,表示A^B最后三位数表示的整数
时间: 2023-05-26 20:03:02 浏览: 52
解法1:暴力求解
对于本题数据范围很小,只有1000以内,可以直接暴力计算A^B,然后取最后三位即可。
C++代码:
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
int ans = 1;
for (int i = 0; i < b; i++) {
ans = ans * a % 1000; // 乘法取模可以防止数据溢出
}
cout << ans << endl;
}
return 0;
}
时间复杂度:O(T * B),其中T为测试数据组数,B为指数的大小(这里是1000以内),可以通过本题。
解法2:快速幂
快速幂是一种快速计算幂的方法,利用指数的二进制拆分,可以将指数降为log级别。本题按照快速幂的思路,对于每一位二进制数,如果该位是1,就将答案乘以底数的当前次幂,否则直接将底数的当前次幂平方即可。
C++代码:
#include <iostream>
using namespace std;
int quick_pow(int a, int b) { // 快速幂
int ans = 1;
while (b) {
if (b & 1) { // 当前二进制位为1
ans = ans * a % 1000;
}
a = a * a % 1000; // 底数的次幂平方
b >>= 1; // 右移一位,去掉当前二进制位
}
return ans;
}
int main() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
int ans = quick_pow(a, b);
cout << ans << endl;
}
return 0;
}
时间复杂度:O(T * logB),其中T为测试数据组数,B为指数的大小(这里是1000以内),可以通过本题。