矩阵快速幂
算法封装模板点击查看代码struct matrix {
vector<vector<int>>a,b;
int n;
matrix (int n1):n(n1),a(n1,vector<int>(n1,0)),b(n1,vector<int>(n1,0)){}
matrix operator-(const mat& T) const {
matrix res(n);
for(int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
res.a = (a - T.a) % mod;
}
return res;
}
matrix operator+(const mat& T) const {
matrix res(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j){
res.a = (a + T.a) % mod;
}
return res;
}
matrix operator*(const mat& T) const {
matrix res(n);
int r;
for (int i = 0; i < n; ++i)
for (int k = 0; k < n; ++k) {
r = a;
for (int j = 0; j < n; ++j)
res.a += T.a * r, res.a %= mod;
}
return res;
}
matrix operator^(int x) const {
matrix res(n), bas(n);
for (int i = 0; i < n; ++i) res.a = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) bas.a = b%mod;
while (x) {
if (x & 1) res = res * bas;
bas = bas * bas;
x >>= 1;
}
return res;
}
};例题
[例题](https://atcoder.jp/contests/abc293/tasks/abc293_e?lang=en）
思路
从题意可知，这个题明显不能用逆元，因为用费马小定理的限制是模数mod必须是质数。
而使用扩展欧几里得求逆元的条件是这个公式中\(ax \equiv 1 \pmod m\)必须满足\(gcd(a,m)==1\)条件，很明显这个题目是不满足的，
所以我们可以考虑使用矩阵加速来解决这个问题，\(x>=1; a=a*a%m; } return res;}int gcd(int a,int b){ return b?gcd(b,a%b):a;}int lcm(int a,int b){ return a*b/gcd(a,b);}struct mat { vectora; int n; mat (int n1):n(n1),a(n,vector(n,0)){} mat operator-(const mat& T) const { mat res(n); for(int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { res.a = (a - T.a) % MOD; } return res; } mat operator+(const mat& T) const { mat res(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j){ res.a = (a + T.a) % MOD; } return res; } mat operator*(const mat& T) const { mat res(n); int r; for (int i = 0; i < n; ++i) for (int k = 0; k < n; ++k) { r = a; for (int j = 0; j < n; ++j) res.a += T.a * r, res.a %= MOD; } return res; } mat operator^(int x) const { mat res(n), bas(n); for (int i = 0; i < n; ++i) res.a = 1; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) bas.a = a % MOD; while (x) { if (x & 1) res = res * bas; bas = bas * bas; x >>= 1; } return res; }};//int e,ne,h,idx,w,in,out;//void add(int a,int b,int c){// e=b,ne=h,w=c,h=idx++;//}signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int _=1; //cin>>_; while(_--){ int a,x,m;cin>>a>>x>>m; MOD=m; mat ma(2); ma.a=a%m,ma.a=1; ma.a=1; ma=(ma^x); cout
页:
[1]