矩阵乘法都忘了啊...
先说题，有结论：gcd(f[n],f[m]) = f[gcd(n,m)]
证明不知道，背着就行了反正就算记住到考场也没法重证一遍
知道结论用矩阵快速幂就ok了
然而递推式我会，怎么实现我忘了...
众所周知，一个n * m的矩阵和m * p的矩阵相乘，生成一个n * p的矩阵
新矩阵的a[i][j] = a[i][k] +a[k][j]，其中1 <= k <= m
然后这两个记住就好写了，其他的和普通快速幂一样了
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<map> #include<cmath> using namespace std; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } typedef int mainint; #define int long long const int mod = 19990208; struct mat { int a[3][3]; int r,c; inline void mem() { memset(a,0,sizeof(a)); r = 0,c = 0; } }; int n,m; mat mul(mat x,mat y) { mat p; p.mem(); for(int i = 0;i < x.r;i++) for(int j = 0;j < y.c;j++) for(int k = 0;k < x.c;k++) (p.a[i][j] += x.a[i][k] * y.a[k][j]) %= mod; p.r = x.r,p.c = y.c; return p; } void power(int b) { mat ans,res; ans.mem(),res.mem(); res.r = res.c = 2; res.a[0][0] = res.a[0][1] = res.a[1][0] = 1; ans.r = 1,ans.c = 2; ans.a[0][0] = ans.a[0][1] = 1; while(b) { if(b & 1) ans = mul(ans,res); res = mul(res,res); b >>= 1; } printf("%lld ",ans.a[0][0]); } int gcd(int x,int y) { return !y ? x : gcd(y,x % y); } mainint main() { int t = read(); while(t--) { int n = read(),m = read(); n = gcd(n,m); if(n <= 2) printf("1 "); else power(n - 2); } }