快速幂
因为幂的性质
比如2^3可以转换成\(2^{1+2}\)也就是\(2^1* 2^2\)
根据这样我们其实就可以把一个大的幂次拆解成几个小的去计算
什么东西能将x拆开成几部分 且相加起来仍是x呢
显然 用二进制
还是以3为例 3 即11 它可以拆成 两个1
而且这两个1还是有关联的 左边这个1是右边那个1的平方
那么 就可以很容易地从低位开始 递推预处理出每一部分的值
（其实只需要算出第一个 然后每往左一位就是上一次的平方）
然而不是每一位都要取的 我们只需要取是1的即可
\(a^b\)中设\(b=2^{t1}+2^{t2}+…+2^{tk}\)(二进制)
其实意思就是\(2^{12}\)可以化成\(2^8*2^4\)
4和8怎么来的
第一轮 \(2^0\) 因为是该位的二进制为0所以不取
第二轮\({2^{0}}^2\)即\(2^2\) 为0 不取
第三轮 \({2^2}^2\)即\(2^4\) 为1 取
第四轮\({2^4}^2\)即 \(2^8\) 为1 取
至于为什么可以每轮都模p
其实就是一个交换律
(a%p)*(b%p)=(a*b)%p
所以何必要求到最大的时候统一模呢 每轮做就好了 还能防止爆数据
int qmi(int a, int b, int p)
{
int res = 1 % p;
while(b)
{
if (b & 1)
res = (long long)res * a % p;
a = (long long)a * a % p;//不管是0还是1 这一位都用过了 a是不断平方的
b>>=1;
}
return res;
}
a^b
💬 评论