快速幂、龟速乘总结
一、快速幂
求 \(a^b\ mod \ p\) 的结果。
\(Code\)
// 快速幂(不加mod)
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
// 快速幂
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (res * a) % MOD;
b >>= 1;
a = a * a % MOD;
}
return res;
}
解释一下：
假如我们需要计算\(2^{10}\),正常的办法是
int s = 1;
for (int i = 1; i <= 10; i++) s = s * 2;
cout << s << endl;
毫无疑问，这个算法是正确的。但它执行的次数是\(10\)次，有没有什么办法可以优化一下运算次数呢？
优化
将\(10\)进行二进制分解\((10)_{10}=(1010)_2\)
这样处理后，从后向前，借助于我们熟悉的数位分离模板，就是遍历二进制的每一位。
此时，我们发现，最左面的数字\(1\)，权值是\(8\)，第三位的数字权值是\(2\)
同时，\(2^8*2^2=2^{10}\)
为什么会有这么神奇的现象呢？其实就是因为幂运算的性质造成：
\[\large 2^{10}=2^{8+2}=2^8*2^2 \]\(Q:\)为啥非得拆成\(8+2\),为啥不拆成\(7+3\)呢？
就是因为类似于 倍增 的办法在计算中好处理呗！
\(a\)在代码中的使命就是：我不管你用不用的上，反正我每次是翻倍！
而枚举\(b\)的每一个数位，就是看看这个位置上的当前\(a\)是不是需要乘进来！幂运算的性质成功的把幂与二进制加法结合起来了。
把倍增的思路\(2,4,8,16,32,...\)这样长上来的，这是因为
\(2^1*2^1=2^2\)
\(2^2*2^2=2^4\)
\(2^4*2^4=2^8\)
\(2^8*2^8=2^{16}\)
\(2^{16}*2^{16}=2^{32}\)
模板题 : \(P1226\) 【模板】快速幂||取余运算
二、龟速乘
求 \(a*b\ mod \ p\) 的结果,\(a,b,p\) 都是 \(10^{18}\) 级别。
\(Code\)
// 龟速乘，快速加
int qadd(int a, int b) {
int res = 0;
while (b) {
if (b & 1) res = (res + a) % MOD;
b >>= 1;
a = (a + a) % MOD;
}
return res;
}
这东西怎么理解呢？
举栗子吧：
\(5*6_{10}=5*(110)_2\)
最右侧的\(0\)对就的权值是\(5^1=5\) ①
右侧第二的\(1\)对就的权值是\(5*2=10\) ②
右侧第三的\(1\)对就的权值是\(10*2=20\) ③
而\(② ③\)对应的位置上有数字\(1\)，有效，\(①\)无效
结果就是\(10+20=30\)