快速幂&幂模

2019-04-13 14:45发布

站内文章 / 模拟电子
10004 0 1628

快速幂

高效率求a的n次方（n>0)，时间复杂度：O（log₂n），常规幂O（n）
递归版
递归版的很好理解

先就按原理直接敲出来（递归总有个终点，a的0次方等于1） int qpow(int a,int n) { if(n==0) return 1; if(n%2==0) return qpow(a,n/2)*pow(a,n/2); else return qpow(a,n/2)*pow(a,n/2)*a; }答案是对了，But，不管奇偶都求了两次qpow(a,n/2)，这还是浪费了时间，因为算了一次你就知道答案了，那么改一改就出来了。 int qpow(int a,int n) { if(n == 0) return 1; int half = qpow(a,n/2); if(n%2) return half*half*a; return half*half; } int main() { printf("%d ", qpow(2,10)); return 0; } 注意溢出，建议使用long long代替int


 非递归版 主要思想是将指数用二进制分析，见度娘


代码实现： int quick_pow(int a,int b) { int res=1; while(b) { if(b & 1) //也可写成b%2==1,判断b二进制里最低位是否为1,为1执行 res *= a; a *= a; b >>= 1; //即b/=2 } return res; }简单的说就是如果b的二进制里某位是1，就把这位的权值乘进去，下面是例子，DOC版下载



快速幂模

有了快速幂基础，幂模也不难了，已知 (a^b)%c  = ((a%c)^b)%c，然后可以把a%c看成a继续模c…… int pow_mod(int a,int b,int c) { int res = 1; a = a % c; while(b) { if(b&1) res = (res * a) % c; a = a * a % c; b >>= 1; } return res; }利用上面那条公式，a事先取一次模减少运算
其他就跟快速幂差不多了，差别在于每次都是乘后取模

模板题1：http://acm.hdu.edu.cn/showproblem.php?pid=1061 模板题2：http://acm.hdu.edu.cn/showproblem.php?pid=2035 最低位就是mod 10 的意思 本题也可以找规律，规律如下
 a 的1次方起
 1: 周期为1, 结尾为1
 2: 周期为4, 结尾为2 4 8 6
 3: 周期为4, 结尾为3 9 7 1
 4: 周期为2, 结尾为4 6
 5: 周期为1, 结尾为5
 6: 周期为1, 结尾为6
 7: 周期为4, 结尾为7 9 3 1
 8: 周期为4, 结尾为8 4 2 6
 9: 周期为2, 结尾为9 1
 0: 周期为1, 结尾为0
有点难找是不？是就乖乖幂模吧。
poj的幂模（带累加的） #include int pow_mod(int a,int b,int c) { int res = 1; a = a % c; while(b) { if(b&1) res = (res * a) % c; a = a * a % c; b >>= 1; } return res; } int main() { int a,b,n,res,z,m,h; scanf("%d",&z); while(z--) { res = 0; scanf("%d%d",&m,&h); while(h--) { scanf("%d %d",&a,&b); res += pow_mod(a,b,m); res %= m; } printf("%d ",res); } return 0; }

矩阵快速幂模

跟整数的一样，只是矩阵乘法不是*号那么简单，时间复杂度依然是O(logn)
下面是Fib%10009的程序
#include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define INF 0x7FFFFFFF #define INT_MIN -(1<<31) #define eps 10^(-6) #define Q_CIN ios::sync_with_stdio(false) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define REV( i , n ) for ( int i = n - 1 ; i >= 0 ; -- i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof (a) ) #define RE freopen("1.in","r",stdin) #define WE freopen("1.out","w",stdout) #define MOD 10009 #define NMAX 10002 #define min(a,b) ((a)>(b)?(b):(a)) struct Matrix { int v[2][2]; }m0; Matrix mul(Matrix A,Matrix B) { Matrix C; REP(i,2) { REP(j,2) { C.v[i][j] = 0; REP(k,2) { C.v[i][j] += A.v[i][k] * B.v[k][j]; } C.v[i][j] %= MOD; } } return C; } Matrix mtPow(Matrix A, ll k) // 求矩阵 A ^ k { if(k == 1) return A; A = mtPow(A, k / 2); if(k % 2 == 0) return mul(A, A); else return mul(mul(A, A), m0); } int main() { ll n; //RE; m0.v[0][0] = 0;m0.v[0][1] = 1; m0.v[1][0] = 1;m0.v[1][1] = 1; while(cin>>n) { if(!n) { cout<<"0"<


热门文章