P1306 斐波那契公约数

题意:求\(Fibonacci\)数列第\(n\)项和第\(m\)项的最大公约数的最后8位。

数据范围:\(1<=n,m<=10^9\)


一些很有趣的性质

引理1:\(F_{(a,b)}=(F_a,F_b)\)

在证明引理1之前,我们得先证明引理2和引理3

引理2:\(F_{m+n}=F_m*F_{n+1}+F_{m-1}*F_n=F_{m+1}*F_n+F_m*F_{n-1}\)

证明:

设正整数\(a>b\)

\(F_a\)

\(=F_{a-1}+F_{a-2}\)

\(=2*F_{a-2}+F_3\)

\(=3*F_{a-3}+2*F_{a-4}\)

\(=F_4*F_{a-3}+F_3*F_{a-4}\)

\(=...\)

\(=F_b*F_{a-b+1}+F_{b-1}*F_{a-b}\)

引理3:\((F_n,F_{n+1})=1\)

证明:

\((F_{n+1},F_n)\)

\(=(F_{n+1}-f_n,F_n)\)

\(=(F_{n-1},F_n)\)

\(=...\)

\(=(F_4,F_3)\)

\(=1\)

证明引理1:

对于\(F_{(a,b)}=(F_a,F_b)\)

右边

\(=(F_b*F_{a-b+1}+F_{b-1}*F_{a-b},F_b)\)

\(=(F_{b-1}*F_{a-b},F_b)\)

\(=(F_{a-b},F_b)\)

即相当于坐标版的gcd了

最后等于\((F_{(a-b)},F_0)\)


直接上矩阵快速幂一顿操作就行了


Code:

#include <cstdio>
#include <cstring>
#define ll long long
const ll mod=100000000;
ll m,n;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
struct matrix
{
ll dx[3][3];
matrix()
{
memset(dx,0,sizeof(dx));
}
matrix friend operator *(matrix n1,matrix n2)
{
matrix n3;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
n3.dx[i][j]=(n3.dx[i][j]+n1.dx[i][k]*n2.dx[k][j])%mod;
return n3;
}
}base,s;
matrix quick_pow(matrix d,ll k)
{
matrix f;
f.dx[1][1]=f.dx[2][2]=1;
while(k)
{
if(k&1)
f=f*d;
d=d*d;
k>>=1;
}
return f;
}
int main()
{
scanf("%lld%lld",&n,&m);
ll k=gcd(n,m);
base.dx[1][1]=base.dx[1][2]=base.dx[2][1]=s.dx[1][1]=s.dx[1][2]=1;
printf("%lld\n",quick_pow(base,k-1).dx[1][1]);
return 0;
}

2018.7.8

05-11 17:04