洛谷题解 P1306 斐波那契公约数 gcd&推式子&矩阵加速递推

_Cheems · 2023-09-30 12:19:13 · 个人记录

题意

求 gcd(fib_n,fib_m)\bmod 1e8 ？

思路

直接求肯定不行的，只能考虑推式子。

定理 1：

证明：

施归纳法证明，假设已知 gcd(fib_{n-1},fib_n)，则：

对于 n=1 的情况，显然有 gcd(fib_{1},fib_2)=1

综上，gcd(fib_n,fib_{n+1})=1

定理 2：

证明：

默认 n\le m。

• 引理：

  fib_m=fib_{m-n-1}*fib_{n}+fib_{m-n}*fib_{n+1}

  考虑一个满足 f_i=f_{i-1}+f_{i-2} 数列，令 f_1=fib_n,f_2=fib_{n+1}。那么必有 f_i=a*f_1+b*f_2，不难发现 a,b 取值的规律。

由引理知：

注意到第二项的前半部分可表示为 fib_n 的乘积，那么还有：

由定理 1 知，gcd(fib_n,fib_{n+1})=1，所以：

结合后两个式子，定理 2 得证。

定理 3：

证明

由定理 2 知：

不断减下去就有：

这正是辗转相除法的递归式，最终我们能得到：

显然 k=gcd(n,m)，证毕。

实现

求 fib_{gcd(n,m)} 即可，矩阵加速递推可以解决此题。

提交记录