- int quick(int a, int b, int c) { int ans = 1; // 记录结果
- a = a % c; // 预处理, 使得 a 处于 c 的数据范围之下
- while (b != 0) {
- if (b & 1) ans = (ans * a) % c; // 如果 b 的二进制位不是 0, 那么我们的结果是要参与运算的
- b >>= 1; // 二进制的移位操作, 相当于每次除以 2, 用二进制看, 就是我们不断的遍历 b 的二进制位
- a = (a * a) % c; // 不断的加倍
- }
- return ans;
- }
对于任何一个整数的模幂运算
a^b%c
对于 b 我们可以拆成二进制的形式
b=b0+b1*2+b2*2^2+...+bn*2^n
这里我们的 b0 对应的是 b 二进制的第一位
那么我们的 a^b 运算就可以拆解成
a^b0*a^b1*2*...*a^(bn*2^n)
对于 b 来说, 二进制位不是 0 就是 1, 那么对于 bx 为 0 的项我们的计算结果是 1 就不用考虑了, 我们真正想要的其实是 b 的非 0 二进制位
那么假设除去了 b 的 0 的二进制位之后我们得到的式子是
a^(bx*2^x)*...*a(bn*2^n)
这里我们再应用我们一开始提到的公式, 那么我们的 a^b%c 运算就可以转化为
(a^(bx*2^x)%c)*...*(a^(bn*2^n)%c)
这样的话, 我们就很接近快速幂的本质了
(a^(bx*2^x)%c)*...*(a^(bn*2^n)%c)
我们会发现令
- A1=(a^(bx*2^x)%c)
- ...
- An=(a^(bn*2^n)%c)
这样的话, An 始终是 A(n-1) 的平方倍 (当然加进去了取模匀速那), 依次递推
快速幂取模
来源: http://www.bubuko.com/infodetail-2496026.html