P1306 斐波那契公约数-白红宇

P1306 斐波那契公约数

阅读量：7052 次

发布时间：2019-06-28

本文共 1490 字，大约阅读时间需要 4 分钟。

矩阵乘法都忘了啊...

先说题，有结论：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
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           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 longconst 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\n",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\n"); else power(n - 2); }}