P1306 斐波那契公约数
对于 Fibonacci 数列：
\[ f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases}\]请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)。
数据规模与约定
- 对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 10^9\)。
Solution:
我们先求Fib
首先我们知道一个东西叫做矩阵乘法，我们构造如下矩阵
\[\begin{equation} A =\begin{bmatrix} F[i] & F[i-1]\\ \end{bmatrix} \end{equation} \]\[\begin{equation} I =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \end{equation} \]\[\begin{equation} A*I =\begin{bmatrix} F[i]+F[i-1] & F[i] \\ \end{bmatrix} \end{equation} \]\(\Longrightarrow\)
\[\begin{equation} A*I =\begin{bmatrix} F[i+1] & F[i] \\ \end{bmatrix} \end{equation} \]然后我们根据辗转相减法求GCD不难推出 F[i+1] 与 F[i] 互质。
然后我们再推一些东西：
设
\[F[i]=a,F[i+1]=b \]\[ \left\{ \begin{aligned} F[i+2]=1a+1b\\ F[i+3]=1a+2b\\ F[i+4]=2a+3b\\ F[i+5]=3a+5b\\ F[i+6]=5a+8b\\ \end{aligned} \right. \]\[F[m]=F[m-i-1]a+F[m-i]b \]\(GCD(F[n],F[m])=GCD(F[n],F[m-n]*F[n+1])\)
\(\Longrightarrow\)
\(GCD(F[n],F[m])=GCD(F[n],F[m-n])\)
利用辗转相减法把这个式子递归下去，就会得到：
\(GCD(F[n],F[m])=F[GCD(n,m)]\)
然后这题就做完了
Code：
#include<bits/stdc++.h>
#define int long long
const int N=105;
const int mod=1e8;
using namespace std;
int n=2,k;
struct Matrix{
int a[N][N];
}ANS;
Matrix operator *(const Matrix &A,const Matrix &B)
{
Matrix res={{0}};
for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)for(int j=1;j<=n;j++)
{
res.a[i][j]+=(A.a[i][k]%mod)*(B.a[k][j]%mod);
res.a[i][j]%=mod;
}
return res;
}
Matrix qpow(Matrix x,int k)
{
Matrix K={{0}};
K.a[1][1]=K.a[1][2]=1;
K.a[2][1]=1;
if(k<=0){for(int i=1;i<=n;i++)x.a[i][i]=1;return x;}
while(k)
{
if(k&1)
{
x=x*K;
}
K=K*K;
k>>=1;
}
return x;
}
void init()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
{
ANS.a[i][j]=0;
}
for(int i=1;i<=n;i++)ANS.a[i][1]=1;
}
int x,y;
int gcd(int x,int y){return y==0 ? x : gcd(y,x%y);}
void work()
{
cin>>x>>y;
init();
x=gcd(x,y);
ANS=qpow(ANS,x-1);
printf("%lld\n",ANS.a[1][1]);
}
#undef int
int main()
{
//freopen("P1939.in","r",stdin);freopen("P1939.out","w",stdout);
work();
return 0;
}