试题 求a^b的后三位数。a,b是整数。 这题也就是计算a^b%1000的值。 解法一 先求出a^b的值，然后计算a^b%m即可。
如果a,b足够大，那么a^b将无法计算出来。所以解法一只适用于a,b都很小的情况。 解法二 解法二会利用如下公式进行计算： 其证明过程如下： 因此a^b%m有如下公式： 按上述公式，就可以避免因为a,b过大，导致溢出的问题。因为每一次相乘都是m-1位数。具体代码如下： [java] view plain copy
private static int cifang(int a, int b) {
if (b == 0) {
return 1;
} else if (b == 1) {
return a % 1000;
} else {
int i = a % 1000;
for (int x = 1; x < b; x++) {
a = a % 1000;
a = a * i;
}
return a % 1000;
}
}
这段代码如果b足够大，计算的耗时依旧非常大。它耗时的关键在于求a^b时，需要进行b次乘法计算。 解法三 快速幂算法——可迅速求出a^b。其主要理论依据如下： 1，当b为偶数时，a^b可以转为a^2的b/2次方。 2，当b为奇数时，a^b可以转为a^2的b/2次方，再乘以a。 而a^2的b/2次方，以可以使用上述方式转为a^4的b/4次方再乘以某个数。代码如下: [java] view plain copy
private static int cifang(int a, int b) {
int s = 1;
while (b > 0) {
if (b % 2 == 1) {//b=b>>1保证了在最后一步肯定会执行该if判断
s = s * a;
}
a = a * a;
b = b >> 1;
}
return s;
}
在每一次进行循环时，如果b为奇数，则a^b可以转为a^2的b/2次方乘以a。所以每一次进行a^2计算时，需要根据b是否为奇数决定是否在最终的结果上乘以a。 a = a*a;此步计算完成后，则a是下一个进行平方运算的数。这样当所有的循环结束后，a就是a^k，其中k是离b最近的，且为2的整数次方的数。 利用快速幂方法可以迅速求出一个数的任意次方。再结合a*b%m=(a%m)*(b%m)%m，就可得出下面计算代码： [java] view plain copy
private static int cifang3(int a, int b) {
int s = 1;
while (b > 0) {
if (b % 2 == 1) {
s = s % 1000;
a = a % 1000;
s = s * a;
}
a = a % 1000;
a = a * a;
b = b >> 1;
}
return s% 1000;
}
上面是利用了：只是要相乘后再取模，就可以先取模再相乘，然后再取模的规律。我们不考虑a最终会用来做什么，反正a就是用来相乘然后取模的，所以可以直接将a进行取模，然后再进行相乘。 同理，对于if判断中的操作也是如此：因为要相乘再取模，所以就先取模再相乘。 用方法二与方法三对5576的1832353248取后三位数进行计算时，方法二耗时7396ms，而方法三只耗时1ms。两者的计算速度差别非常大，因为方法二是进行了1832353248次循环，而方法三进行了log以2为底1832353248的对数次循环。两者差别相当巨大。 转载自：https://blog.csdn.net/java_c_android/article/details/55802041