【原创】【分治】快速取幂与模取幂

模取幂

时间限制: 1 Sec  内存限制: 64 MB 提交: 468  解决: 172

题目描述

输入b，p，k的值，求b^p mod k的值。其中b，p，k为整型数。 b,p均不超过整型范围，k^2不超过整型。

输入

第1行:3个空格分开的整数b, p, k

输出

第1行：1个数表示运算结果。

样例输入

2 10 9

样例输出

7 首先，这道题肯定不能直接pow求，也不能用循环，肯定超时，再不然就超限。 那么，a^b怎么求呢？ 我们知道， 那么，a的n次方是不是也可以拆分呢？ 当然可以，方案如下： 所以我们就得到了一个简单的关系式，接下来就是写程序验证的时间了！ 至于模取幂，取幂就可以了呗！ 详见代码： #include<iostream> using namespace std; long long a,c,k; long long double_cut(long long a,long long c) { if(c==1) return a%k; else if(c==0) return 1%k; else if(c%2==0) return (double_cut(a,c/2)%k)*(double_cut(a,c/2)%k); else return ((double_cut(a,(c-1)/2)%k)*(double_cut(a,(c-1)/2)%k)*(a%k)); } int main() { cin>>a>>c>>k; cout<<double_cut(a,c)%k; } 但是，通过实践，其实这个快速幂并没有快到哪里去，我们还需要更快的代码！ 原文见 此← 算(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，就不用考虑了，只需要看剩下的1可以了。 （这也解释了前文的代码慢的原因，浪费了很多时间在没有用的1） 那么假设除去了b的0的二进制位之后我们得到的式子是   a^(bx*2^x)*...*a(bn*2^n)   取模，则有(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)的平方倍（记得取模） 详见代码： int double_cut(int a,int b,int c) { int ans=1;//初始化，ans=1 a%=c;//让a在mod c 范围内 while(b) { if(b&1) ans=(ans*a)%c; //如果b的二进制位不是0，那么它就要乘进来 //&是与运算，这里：如果b的二进制最后一位和1的二进制最后一位都是1，返回1 b>>=1; //二进制的右移操作，相当于每次除以2，就是把b的二进制最后一位丢掉，前面的往右补位 a*=a; a%=c; //不断的加倍 } return ans; }