正题

题目链接：

---

题目大意

求出第x项和第y项斐波那契额数的最大公约数。

---

解题思路

首先第x项和第y项斐波那契额数的最大公约数就是第gcd(x,y)项斐波那契额数。

但是样例还是很大，于是就得用矩阵乘法加速递推：

斐波那契数

[Fibn,Fibn+1]=[Fibn−1,Fibn]∗[0,1][1,1][Fibn,Fibn+1]=[Fibn−1,Fibn]∗[0,1][1,1]

快速幂就好了

---

代码

#include
     
      #include
      
       #include
       
        using namespace std;int n,m,nm,p,a[2],f[2][2],c[2],c1[2][2];int main(){    scanf("%d%d",&n,&m);    nm=__gcd(n,m);p=1e8;    nm--;    a[0]=1;a[1]=1;    f[0][0]=0;f[0][1]=1;    f[1][0]=1;f[1][1]=1;//初始化    int ans=1;    while (nm)    {
             if (nm&1)        {
                 memset(c,0,sizeof(c));            for (int j=0;j<2;j++)              for (int k=0;k<2;k++)                c[j]=(c[j]+(long long)f[k][j]*a[k])%p;//矩阵乘法            memcpy(a,c,sizeof(c));        }        memset(c1,0,sizeof(c1));        for (int i=0;i<2;i++)          for (int j=0;j<2;j++)            for (int k=0;k<2;k++)              c1[i][j]=(c1[i][j]+(long long)f[i][k]*f[k][j])%p;//矩阵乘法        memcpy(f,c1,sizeof(c1));        nm>>=1;//快速幂    }    printf("%d",a[0]);}