本文共 1390 字,大约阅读时间需要 4 分钟。
我们现在知道了快速幂取模算法的强大了,我们现在来看核心原理:
对于任何一个整数的模幂运算
a^b%c
对于b我们可以拆成二进制的形式
b=b0+b1*2+b2*2^2+...+bn*2^n
这里我们的b0对应的是b二进制的第一位
那么我们的a^b运算就可以拆解成
a^b0*a^b1*2*1...*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)的平方倍(当然加进去了取模匀速那),依次递推
我们可以得出以下的结论:
1.如果b是偶数,我们可以记
k = a2 mod c,那么求(k)b/2 mod c就可以了。2.如果b是奇数,我们也可以记 ((k)b/2 mod c × a ) mod c 就可以了。
现在我们来考虑实现它:
迭代法:
1 int fast_pow(int a,int b,intc)2 {3 int ans=1; ///记录结果
4 a=a%c; ///预处理,使得a处于c的数据范围之下
5 while(b!=0)6 {7 if(b&1)///奇数
8 {9 ans=(ans*a)%c;///消除指数为奇数的影响
10 }11 b>>=1; ///二进制的移位操作,不断的遍历b的二进制位
12 a=(a*a)%c; ///不断的加倍
13 }14 returnans;15 }
递归法:
1 ll fast_pow(ll x,ll n,ll p)2 {3 ll temp;4 x=x%p;5 if(n==0)///终止条件
6 {7 return 1;8 }9 temp=fast_pow((x*x)%p,n>>1,p);10 if(n&1)11 {12 temp =temp*x%p;///消除指数为奇数的影响
13 }14 return temp%p;15 }
在这里还要进行几点说明:
1.二进制的几个运算符& 和 >> 。
&运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶,x&1==0为偶,x&1==1为奇。
>>运算比较单纯,二进制去掉最后一位,移位操作,不断遍历b的二进制位。
2. a=(a*a)%c这一步的作用是用来不断的加倍,在先不看同余定理的情况下,a*a==a^2,下一步再乘,就是a^2*a^2==a^4,然后同理 a^4 * a4 =a^8 .........?是不是做到了
a-->a^2-->a^4-->a^8-->a^16-->a^32.......指数正是 2^i 啊,再看上面的例子,a¹¹ = a^(2^0) * a^(2^1) * a^(2^3),这三项是不是完美解决了,快速幂就是这样。
转载地址:http://loydy.baihongyu.com/