快速幂，矩阵快速幂（模板）
1，整数快速幂：
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | ///快速幂 a^b int qpow( int a, int b) { if(a== 0) return 0; int ans= 1; while(b) { if(b& 1) ans=a; ///和快速乘法的区别 b>>= 1; ///等价于b=b>>1和b=b/2; a=a; ///区别，同上 } return ans; } |
2，含有取余的整数快速幂：
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> using namespace std; int pw( int x, int y, int p) { if (!y) { return 1; } int res = pw((x x) % p, y / 2, p); if (y & 1) //判断奇偶性 y&1==1为奇数,反之为偶数 { res = res x % p; } return res; } int main() { int x, y, p; cin >> x >> y >> p; cout << pw(x, y, p) << endl; return 0; } |
或者
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | ///a^b结果取余mod int qpow_mod( int a, int b, int mod) { if(a== 0) return 0; int ans= 1; while(b) { if(b& 1) ans=(ans%mod)(a%mod); ///如果确定数据不会爆的话，可写成 ans=a%=mod; b>>= 1;a=a%=mod; ///等价于a=(a%mod)(a%mod)，且将一个模运算通过赋值代替，提高了效率 } return ans%mod; ///数据不会爆的话，这里的%运算会等价于第5中不断重复的 ans%mod } ///1.(ab) mod M=(a mod M)(b mod M) mod M; ///2.(a+b) mod M=(a mod M+b mod M) mod M; ///3.(a/b) mod M=(a*b^(M-2)) mod M;（费马小定理） |
3，矩阵快速幂：
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> using namespace std; int N; ///以33的矩阵为例 struct matrix { int a[ 3][ 3]; } origin,res; matrix multiply(matrix x,matrix y) { ///矩阵乘法 matrix temp; memset(temp.a, 0, sizeof(temp.a)); for( int i= 0; i< 3; i++) { for( int j= 0; j< 3; j++) { for( int k= 0; k< 3; k++) { temp.a[i][j]+=x.a[i][k]y.a[k][j]; } } } return temp; } void init() { ///初始化，产生随机数 printf( “随机数组如下:\n”); for( int i= 0; i< 3; i++) { for( int j= 0; j< 3; j++) { origin.a[i][j]=rand()% 10; printf( “%8d”,origin.a[i][j]); } printf( “\n”); } printf( “\n”); memset(res.a, 0, sizeof(res.a)); res.a[ 0][ 0]=res.a[ 1][ 1]=res.a[ 2][ 2]= 1; ///将res.a初始化为单位矩阵 } void calc( int n) { ///快速幂核心代码 while(n) { if(n& 1) res=multiply(res,origin); n>>= 1; origin=multiply(origin,origin); } printf( “%d次幂结果如下：\n”,n); for( int i= 0; i< 3; i++) { for( int j= 0; j< 3; j++) printf( “%8d”,res.a[i][j]); printf( “\n”); } printf( “\n”); } int main() { ///主函数 while(cin>>N) { init(); calc(N); } return 0; } |
￡神魔★判官ぃ
今天药忘吃喽~
曾经终败给现在
左手的ㄟ右手
╰+攻爆jí腚メ
小鱼儿
还没有评论，来说两句吧...