洛谷P1306 斐波那契公约数(数论+证明)
题目大意:给你一个n,m(1<=n,m<=1e9),求__gcd(F[n],F[m])%1e8.
首先我在这里提出一个数论定理:__gcd(F[n],F[m])=F[__gcd(n,m)].
其实在知道这个数论定理后这题就变得非常容易了,只需要求出n,m的最大公约数,然后利用矩阵加速求F[__gcd(n,m)]对1e8取模即可.
但是这个定理为什么是正确的呢?
证明如下:
设n<m,且F[n]=a,F[n+1]=b
F[n+2]=a+b
F[n+3]=a+2*b=F[n]+2*F[n+1]
F[n+4]=2*a+3*b=2*F[n]+3*F[n+1]
不难发现 F[n+x