洛谷P1306斐波那契公约数 题解

题目链接

已知$f_n$为斐波那契数列第$n$项,给定数字$a$和$b$,求$\gcd(f_a,f_b)$。

关于本题有结论:

以下所有$f_n$为斐波那契数列第$n$项,$f_n=f_{n-1}+f_{n-2}$,其中$f_0=0,f_1=1$

下面给出证明过程,首先证明几个定理:

$\textbf{定理1: } \gcd(f_n,f_{n-1})=1\\\textbf{证明:}\\ \gcd(f_n,f_{n-1})\\ =\gcd(f_n-f_{n-1},f_{n-1})\\ =\gcd(f_{n-1},f_{n-2})\\ \cdots\cdots\\=\gcd(f_2,f_1)=1$

由此可知斐波那契数列任意相邻两项互质。

$\textbf{定理2: } f_{n+m}=f_{n-1}f_m+f_nf_{m+1} \\\textbf{证明:}\\当m=1时,f_{n+1}=f_{n-1}f_1+f_nf_2显然成立.\\当m=k时,f_{n+k}=f_{n-1}f_k+f_nf_{k+1}\\当m=k-1时,f_{n+k-1}=f_{n-1}f_{k-1}+f_nf_k\\当m=k+1时,f_{n+k+1}\\=f_{n+k-1}f_1+f_{n+k}f_2\\=f_{n-1}f_{k-1}+f_nf_k+f_{n-1}f_k+f_nf_{k+1}\\=f_{n-1}(f_k+f_{k-1})+f_n(f_{k+1}+f_k)\\=f_{n-1}f_{k+1}+f_nf_{(k+1)+1}\\证毕$

$\textbf{定理3: } \gcd(f_{n+m},f_n)=\gcd(f_m,f_n)\\\textbf{证明: }\\应用定理2,\gcd(f_{n+m},f_n)\\=\gcd(f_{n-1}f_m+f_nf_{m+1},f_n)\\=\gcd(f_{n-1}f_m,f_n)\\根据定理1,由于\gcd(f_{n-1},f_n)=1,\\上式=\gcd(f_m,f_n)$

$\textbf{变形: } \gcd(f_{n-m},f_m)=\gcd(f_m,f_n)\\\textbf{证明: }\\\gcd(f_n,f_m)\\=\gcd(f_{n-m+m},f_m)\\=\gcd(f_{n-m-1}f_m+f_{n-m}f_{m+1},f_m)\\=\gcd(f_{n-m}f_{m+1},f_m)\\=\gcd(f_{n-m},f_m)$

现在证明本题结论$\gcd(f_n,f_m)=f_{\gcd(n,m)}$,应用定理3的变形,不妨设$n>m$

$\gcd(f_m,f_n)\\=\gcd(f_{n-m},f_{m})\\=\gcd(f_{n-\lfloor\frac{n}{m}\rfloor\times m},f_m)\\=\gcd(f_{(n \mod m)},f_m)\\令n_x=n \mod m,显然m>n_x\\上式=\gcd(f_{n_x},f_m)=\gcd(f_{n_x},f_{(m \mod n_x)})$

不难发现,上面的过程实际上是在辗转相除,那么令上式递归,直到一项为0,另一项为$\gcd(n,m)$,即

$\gcd(f_m,f_n)=\gcd(f_{\gcd(m,n)},f_0)=f_{\gcd(m,n)}$

那么,我们可以直接输出$f_{\gcd(n,m)}$,但是,本题直接使用循环求斐波那契数列是会TLE的,我们需要用矩阵来优化。

对于斐波那契数列,可以写成矩阵的形式的递推公式:

退着推回去:

最后我们发现只要用矩阵乘法和快速幂就可以很快求出斐波那契数列的任意项了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cstring>

using LL=long long;

using std::cerr;
using std::endl;

const int mod=1e8;
const int maxn=30;

struct Matrix
{
int r,c;
LL data[maxn][maxn];

Matrix(int r,int c):r(r),c(c)
{
memset(data,0,sizeof data);
}

LL *operator[](int p)
{
return data[p];
}

Matrix operator *(const Matrix &other) const
{
Matrix ans(this->r,other.c);
for(int i=1;i<=this->r;i++)
for(int j=1;j<=other.c;j++)
for(int k=1;k<=this->c;k++)
ans[i][j]=(ans[i][j] + this->data[i][k] * other.data[k][j])%mod;
return ans;
}
};

Matrix ksm(Matrix base,LL power)
{
Matrix ans(base.r,base.c);
for(int i=1;i<=std::min(ans.r,ans.c);i++)
ans[i][i]=1;
for(;power;power>>=1,base=base*base)
if(power&1)
ans=ans*base;
return ans;
}

LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}

LL fib(int n)
{
if(n<=2)
return n==2?1:(n==1?1:0);
Matrix base(2,2),init(1,2);
base[1][1]=1,base[1][2]=1;
base[2][1]=1,base[2][2]=0;
init[1][1]=1;
init[2][1]=1;
Matrix ans(1,2);
ans=ksm(base,n-2)*init;
return ans[1][1]%mod;
}

int main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%lld\n",fib(gcd(n,m)));
return 0;
}