计算 a^n % b，其中 a，b 和 n 都是 32 位的整数。
样例
例如 2^31 % 3 = 2
例如 100^1000 % 1000 = 0
挑战
O(logn)
思路
a ^ 2n = (a ^ n) * (a ^ n)
a ^ 2n + 1 = (a ^ n) * (a ^ n) * a
把幂次方拆成一半乘一半
代码
class Solution {
/*
* @param a, b, n: 32bit integers
* @return: An integer
*/
public int fastPower(int a, int b, int n) {
if (n == 1) {
return a % b;
}
if (n == 0) {
return 1 % b;
}
// 用 long 类型不会有精度损失，结果准确
long product = fastPower(a, b, n >> 1);
product = (product * product) % b;
if ((n & 0x1) == 1) {
product = (product * a) % b;
}
return (int) product;
}
}
注意
- 位运算的左移替代除 2 和与运算替代取余更有效率
- 答案是最终版本的优化算法，笨方法是用 for 循环从 1 循环到 n，比较没效率，但无论哪种做法都需要考虑底数为 0 并且幂次方为负的特殊情形。
下面是剑指offer书上的原话
代码
描述
