先看这道题的歪解 可知当n>mn>mn>m时，fibn=fibm+1fibn−m+fibmfibn−m−1fib_{n}=fib_{m+1}fib_{n-m}+fib_{m}fib_{n-m-1}fibn =fibm+1 fibn−m +fibm fibn−m−1 . ∴gcd⁡(fibn,fibm)=gcd⁡(fibm+1fibn−m+fibmfibn−m−1,fibm)\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m}+fib_{m}fib_{n-m-1},fib_m)∴gcd(fibn ,fibm )=gcd(fibm+1 fibn−m +fibm fibn−m−1 ,fibm ). 又∵fibmfibn−m∣fibm,\because fib_mfib_{n-m}|fib_m,∵fibm fibn−m ∣fibm , ∴gcd⁡(fibn,fibm)=gcd⁡(fibm+1fibn−m,fibm)\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m},fib_m)∴gcd(fibn ,fibm )=gcd(fibm+1 fibn−m ,fibm )(辗转相除法). 又∵gcd⁡(fibn,fibn−1)\because \gcd(fib_n,fib_{n-1})∵gcd(fibn ,fibn−1 ) =gcd⁡(fibn−2,fibn−1)=\gcd(fib_{n-2},fib_{n-1})=gcd(fibn−2 ,fibn−1 )(辗转相除法) =gcd⁡(fibn−2,fibn−3)=\gcd(fib_{n-2},fib_{n-3})=gcd(fibn−2 ,fibn−3 )(辗转相除法) =gcd⁡(fibn−4,fibn−3)=\gcd(fib_{n-4},fib_{n-3})=gcd(fibn−4 ,fibn−3 )(辗转相除法) =gcd⁡(fibn−4,fibn−5)=\gcd(fib_{n-4},fib_{n-5})=gcd(fibn−4 ,fibn−5 )(辗转相除法) =…=…=… =gcd⁡(fib1,fib2)=\gcd(fib_{1},fib_{2})=gcd(fib1 ,fib2 ) =1=1=1, ∴gcd⁡(fibn,fibm)=gcd⁡(fibm+1fibn−m,fibm)=gcd⁡(fibn−m,fibm)\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m},fib_m)=\gcd(fib_{n-m},fib_m)∴gcd(fibn ,fibm )=gcd(fibm+1 fibn−m ,fibm )=gcd(fibn−m ,fibm ). 嗯？怎么有点眼熟？ 那这样不就可以和普通的求最大公因数一样了吗！ ∴gcd⁡(fibn,fibm)=gcd⁡(fibn−m,fibm)=gcd⁡(fibnmod  m,fibm)=gcd⁡(fibgcd⁡(n,m),fibgcd⁡(n,m))=fibgcd⁡(n,m)\therefore \gcd(fib_n,fib_m)=\gcd(fib_{n-m},fib_m)=\gcd(fib_{n\mod m},fib_m)=\gcd(fib_{\gcd(n,m)},fib_{\gcd(n,m)})=fib_{\gcd(n,m)}∴gcd(fibn ,fibm )=gcd(fibn−m ,fibm )=gcd(fibnmodm ,fibm )=gcd(fibgcd(n,m) ,fibgcd(n,m) )=fibgcd(n,m) . 所以，我们只需要求fibgcd⁡(n,m)fib_{\gcd(n,m)}fibgcd(n,m) 的值就行了 矩阵快速幂： 时间复杂度：O(log⁡2n)O(\log_2n)O(log2 n). 乘法分治： 时间复杂度：O(log⁡2n)O(\log^2n)O(log2n).