快速冪利用二進制

復雜度 log級

#include <cstdio> #include <iostream> #include <string> #include <bits/stdc++.h>using namespace std; typedef long long ll; typedef unsigned long long ull;int q_power(int a,int b,int c) {int r=1;a%=c;while (b) {if (b&1) {r=(r*a)%c;}a=(a*a)%c;b>>=1;}return r; }int a,b,c; int main () {cin>>a>>b>>c;cout<<q_power(a,b,c);return 0; }

附帶上矩陣快速冪以及

矩陣快速冪求斐波那契數列：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int mod = 10000; const int maxn = 35; int N; struct Matrix {int mat[maxn][maxn];int x, y;Matrix() {memset(mat, 0, sizeof(mat));for (int i = 1; i <= maxn - 5; i++) mat[i][i] = 1;} }; inline void mat_mul(Matrix a, Matrix b, Matrix &c) {memset(c.mat, 0, sizeof(c.mat));c.x = a.x; c.y = b.y;for (int i = 1; i <= c.x; i++) {for (int j = 1; j <= c.y; j++) {for (int k = 1; k <= a.y; k++) {c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod;c.mat[i][j] %= mod;}}}return ; } inline void mat_pow(Matrix &a, int z) {Matrix ans, base = a;ans.x = a.x; ans.y = a.y;while (z) {if (z & 1 == 1) mat_mul(ans, base, ans);mat_mul(base, base, base);z >>= 1;}a = ans; } int main() {while (cin >> N) {switch (N) {case -1: return 0;case 0: cout << "0" << endl; continue;case 1: cout << "1" << endl; continue;case 2: cout << "1" << endl; continue;}Matrix A, B;A.x = 2; A.y = 2;A.mat[1][1] = 1; A.mat[1][2] = 1;A.mat[2][1] = 1; A.mat[2][2] = 0;B.x = 2; B.y = 1;B.mat[1][1] = 1; B.mat[2][1] = 1;mat_pow(A, N - 1);mat_mul(A, B, B);cout << B.mat[1][1] << endl;}return 0; }

順便來一發

矩陣乘法：

/*假設 A 是 m*p 的矩陣 , B 是 p*n 的矩陣記 C = AB (C 是 矩陣 A與B的乘積)那么 C 是 m*n 的矩陣 */ for (int i = 1;i <= m;++i)//A的行 {for (int j = 1;j <= n;++j)//B的列 {for (int k = 1;k <= p;++k)//通過公式求C {C[i][j] += A[i][k]*B[k][j];}} } #include<iostream> #include<cmath> #include<cstring> using namespace std; typedef long long LL; const LL mod = 1000000007; /*矩陣快速冪求斐波那契數列輸入 n 輸出 f[n] */ struct Mat {LL mat[2][2]; }; Mat operator * (Mat a,Mat b)//矩陣乘法 {Mat c;for (int i = 0;i < 2;++i){for (int j = 0;j < 2;++j){c.mat[i][j] = 0;for (int k = 0;k < 2;++k){c.mat[i][j] = ((a.mat[i][k]*b.mat[k][j])%mod + c.mat[i][j])%mod;}}}return c; } Mat operator ^ (Mat a,LL k)//矩陣冪 {Mat c;for (int i = 0;i < 2;++i){for (int j = 0;j < 2;++j){c.mat[i][j] = (i==j);//初始化為單位矩陣 }}//據說任何矩陣乘以單位矩陣其值不會變for (;k;k>>=1){if (k&1) c = c*a;a = a*a;}return c; } int main() {LL n;while (cin>>n){Mat a;a.mat[0][0] = 1,a.mat[0][1] = 1,a.mat[1][0] = 1,a.mat[1][1] = 0;Mat fn = a^n;cout<<fn.mat[0][1]<<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/codemaker-li/p/9899049.html

總結

以上是生活随笔為你收集整理的快速幂,矩阵乘法,矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。