P1306斐波那契公约数

differential · 2018-11-02 10:52:33 · 题解

对于斐波那契数，有以下性质：

1. (f_n,f_{n-1})=1

证明：
(f_n,f_{n-1})=(f_{n-1},f_n-f_{n-1})=(f_{n-1},f_{n-2})=(f_2,f_1)=1
2. f_{m+n}=f_{m+1} f_{n} + f_{m} f_{n-1}

证明（归纳法）：
首先，易得出m,n是等效的。
设f_0=0,则对于m=n=1,f_{m+n}=f_{m+1} f_{n} + f_{m} f_{n-1}成立。
设对于m,n\le k, f_{m+n}=f_{m+1} f_{n} + f_{m} f_{n-1}成立，
则当n=k+1:
f_{m+n}=f_{m+k+1}=f_{m+k}+f_{m+k-1}=f_{m+1}f_{k}+f_{m}f_{k-1}+f_{m+1}f_{k-1}+f_{m}f_{k-2} 证毕。 ### 3. $f_m$ $mod$ $f_n$ $=0$ $\rightleftharpoons$ $m$ $mod $ $n=0$ 证明： > 引理：$ an\equiv bn\ mod \ m$,则$a\equiv b\ mod \ \frac{m}{(m,n)}$ 斐波那契数列在模$f_n$意义下的序列$s_n$为$1,1,\ldots,f_{n-1},0,f_{n-1},f_{n-1},\ldots,0,$则对于$s_k=0$，有:$\{s_{k+1},\cdots ,s_{k+n}\}=\{s_{k-n+1}\cdot f_{n-1} \ mod\ f_n,\cdots,s_k\cdot f_{n-1} \ mod\ f_n\}$, 即下一段序列相当于上一段序列在模意义下乘以$f_{n-1}$,又因为$s_n=f_n \ mod \ f_n=0$,所以$s_{t\cdot n}=0$. 设$x\cdot f_{n-1} \equiv 0\cdot f_{n-1} \ mod\ f_n$,则由性质1与引理得:$x\equiv 0 \ mod\ (\frac{f_n}{(f_n,f_{n-1})}=f_n)$，即$s_k=0$当且仅当$f_k\ mod\ f_n=0$ 由此可得出，$f_m\ mod\ f_n=0$当且仅当$s_m=0$,即$m=t \cdot n.$ 证毕。 ### 4. $(f_m,f_n)=f_{(m,n)} $ 证明： $(f_m,f_n)=(f_{(m-n)+n},f_n)=(f_{m-n+1}f_n+f_{m-n}f_{n-1},f_n)=(f_{m-n}f_{n-1},f_n)$ $\because (f_{n-1},f_n)=1 $ $ \therefore (f_{m-n}f_{n-1},f_n)=(f_{m-n},f_n)=f_{(m,n)} $ 证毕。
利用性质4，我们把问题转化为求f_{(m,n)},由于m,n\le 1e9,我们需要用矩阵快速幂加速递推。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define re register int
#define rec(i,j,k) for(re (i)=(j);(i)<=(k);(i)++)
#define mem(s,k) memset(s,(k),sizeof s)
typedef long long LL;
const int maxX=2,maxY=2;
const LL mod=1e8;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
LL tmp[maxX][maxY],A[maxX][maxY],B[maxX][maxY],ans[maxX][maxY];
#define cpy(A1,A2,n,m)\
{\
for(re i=0;i<n;i++)for(re j=0;j<m;j++)A2[i][j]=A1[i][j];\
}
#define mul(A1,A2,A3,n,m,q)\
{\
for(re i=0;i<n;i++)\
 for(re j=0;j<q;j++)\
 {\
    tmp[i][j]=0;\
    for(re k=0;k<m;k++)tmp[i][j]=(tmp[i][j]+A1[i][k]*A2[k][j])%mod;\
 }\
cpy(tmp,A3,n,q);\
}
void fpow(int y)
{
while(y)
{
    if(y&1)mul(ans,A,ans,2,2,2);
    mul(A,A,A,2,2,2);
    y>>=1;
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
ans[0][0]=ans[1][1]=1;
A[0][0]=A[0][1]=A[1][0]=1;
B[0][0]=B[1][0]=1;
fpow(gcd(n,m)-1);
mul(ans,B,B,2,2,1);
printf("%lld",B[1][0]);
return 0;
}

blog:https://www.cnblogs.com/Personal-Reality/p/9894672.html

P1306斐波那契公约数

1. (f_n,f_{n-1})=1

2. f_{m+n}=f_{m+1} f_{n} + f_{m} f_{n-1}