斐波那契公约数
题目描述
对于 Fibonacci 数列：
\[ f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases}\]请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)。
输入格式
一行两个正整数 \(n\) 和 \(m\) 。
输出格式
输出一行一个整数，代表 \(f_n\) 和 \(f_m\) 的最大公约数。答案请对 \(10^8\) 取模。
样例 #1
样例输入 #1
4 7
样例输出 #1
1
提示
数据规模与约定
- 对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 10^9\)。
不妨令 n < m
\[f[n+2] = f[n] + f[n+1]; \]\[f[n+3] = f[n+1] + f[n+2] = 2 * f[n+1] + f[n]; \]\[f[n+4] = f[n+2] + f[n+3] = 2 * f[n+2] + f[n+1] = 3 * f[n+1] + 2 * f[n] \]\[f[n+5] = 5 * f[n+1] + 3 * f[n] \]发现如下规律
\[f[n+t] = f[t] * f[n+1] + f[t-1] * f[n] \]将m代进去就有
\[f[m] = f[m-n] * f[n+1] + f[n-m-1] * f[n] \]那么要求的就是\(Gcd(f[n] , f[m]) = Gcd(f[n] , f[m-n]*f[n+1] + f[n-m-1] * f[n])\)
然后由于\(f[n] \ \ | \ \ f[n-m-1] * f[n]\)
\(Gcd(f[n] , f[m]) = Gcd(f[n] , f[m-n]*f[n+1])\)
再因为\(Gcd(f[n] , f[n+1]) = 1\)
所以\(Gcd(f[n] , f[m]) = Gcd(f[n] , f[m-n])\)
发现n，m和求解\(Gcd(n,m)\)的辗转相除法一样，所以\(Gcd(f[n] , f[m]) = f[Gcd(n,m)]\)
关于\(Gcd(f[n] , f[n+1]) = 1\)的证明
\[Gcd(f[n] , f[n+1]) = Gcd(f[n] , f[n] + f[n-1]) \]\[Gcd(f[n] , f[n+1]) = Gcd(f[n-1] , f[n]) \]以此类推
\[Gcd(f[n] , f[n+1]) = Gcd(f[1] , f[2]) = 1 \]代码只需用矩阵优化一下递推即可，略。
标签：Gcd,Luogu,样例,斐波,leq,P1306,公约数,那契 From： https://www.cnblogs.com/R-Q-R-Q/p/16916622.html