洛谷P1306 斐波那契公约数

题意：给出n，m（n,m<=10^9），求GCD（F_n，F_m）

F为斐波那契数组

GCD（F_n，F_m）=F_{GCD（n，m）}

矩阵快速幂加速求F。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,mod=1e8;
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
struct node{
    long long a[3][3];
}ans,tmp;
node cheng(node a,node b){
    node c;
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++)c.a[i][j]=0;
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                c.a[j][k]=(c.a[j][k]+a.a[j][i]*b.a[i][k]%mod)%mod;
            }
        }
    }
    return c;
}
int main()
{
    scanf("%d%d",&n,&m);
    int d=gcd(n,m);
    ans.a[1][1]=1,ans.a[1][2]=1;
    tmp.a[1][1]=tmp.a[1][2]=tmp.a[2][1]=1;
    if(d==1||d==2){
        printf("1
");
        return 0;
    }
    d-=2;
    while(d){
        if(d&1)ans=cheng(ans,tmp);
        tmp=cheng(tmp,tmp);
        d>>=1;
    }
    printf("%lld
",ans.a[1][1]);
    return 0;
}