题解 P1306 [斐波那契公约数]
首先,斐波那契数列相邻项的gcd=1.假设不为1的话,可以推出之前所有相邻项gcd均不为1,但gcd(f(1),f(2))=gcd(1,1)=1,矛盾,所以相邻项gcd=1.
然后,不妨设n<m,设第f(n)与f(n+1)为a,b,则有:
x f(x)
0 0 1 1 2 1 3 2 ... n a n+1 b
n+2 a+b
n+3 a+2b
n+4 2a+3b
m f(m-n-1)a+f(m-n)b
根据gcd(m,n)=gcd(n,m%n),则
gcd(f(m),f(n))
=gcd(f(n),f(m)%f(n))
=gcd(a,f(m-n)b)
因为a和b是相邻项,gcd