洛谷P1306 斐波那契公约数题解

题意：

对于 Fibonacci 数列：

\[ f_i = f_{i - 1} + f_{i - 2} + [i = 1] \] 请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)。

输入格式：

一行两个正整数 \(n\) 和 \(m\) 。

输出格式：

输出一行一个整数，代表 \(f_n\) 和 \(f_m\) 的最大公约数。答案请对 \(10^8\) 取模。

数据范围：

保证 \(1 \leq n, m \leq 10^9\)。

结论1：\(\gcd(f_n, f_{n-1}) = 1\)

证明： \[ \gcd(f_n,f_{n-1}) = \gcd(f_{n-2},f_{n-1}) = \cdots = \gcd(f_1,f_2) = 1 \quad \square \]

结论2：\(f_{n + m} = f_{m+1}f_n + f_{m}f_{n-1}\)

证明：考虑归纳法。显然 \(n=m=1\) 时结论成立。设对于 \(n,m \le k\) 结论成立，考虑 \(n=k+1\) 的情况 \[ \begin{aligned} f_{m+n}&=f_{m+k+1} \\[6pt]&=f_{m+k}+f_{m+k-1} \\[6pt]&=f_{m+1} f_k+f_m f_{k-1}+f_{m+1} f_{k-1}+f_m f_{k-2} \\[6pt]&=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2}) \\[6pt]&=f_{m+1}f_{k+1}+f_{m}f_{k} \end{aligned} \] 则结论对 \(n=k+1\) 同样成立，证毕。

结论3：\(f_m\equiv 0 \pmod{f_n}\) 当且仅当 \(m \equiv 0 \pmod{n}\)

证明：首先有引理：若 \(an \equiv bn \pmod{m}\) 则 \(a\equiv b \pmod{\frac{m}{\gcd(n,m)}}\)

斐波那契数列在模 \(f_n\) 意义下的序列 \(s_n\) 为 \(1,1,\cdots,f_{n-1},0,f_{n-1},f_{n-1},\cdots,0\)

则对于 \(s_k = 0\) 的 \(k\) 有 \[ \left\{s_{k+1},~\cdots,~s_{k+n}\right\} = \left\{s_{k-n+1}\cdot f_{n-1} \bmod f_n,~\cdots,~s_k\cdot f_{n-1}\bmod f_n\right\} \] 即下一段序列等于上一段序列在模 \(f_n\) 意义下称 \(f_{n-1}\) ，又因为 \(s_n = f_n \bmod f_n = 0\) ，所以 \(s_{tn} = 0\)

设 \(x \cdot f_{n-1} \equiv 0 \cdot f_{n-1}\pmod{f_n}\) ，则 \(x \equiv 0 \pmod{\frac{f_n}{\gcd(f_n,f_{n-1})}=f_n}\)

即 \(s_k = 0\) 当且仅当 \(f_k \equiv 0 \pmod{f_n}\) 。因此 \(f_m \equiv 0 \pmod{f_n}\) 当且仅当 \(s_m = 0\) ，即 \(m = tn\) 。\(\square\)

结论4：\(\gcd(f_n, f_m) = f_{\gcd(n,m)}\)

证明： \[ \begin{aligned} \gcd(f_m, f_n) &= \gcd(f_{(m-n)+n}, f_n) \\[6pt]&=\gcd(f_{m-n+1} f_n+f_{m-n} f_{n-1}, f_n) \\[6pt]&=\gcd(f_{m-n}f_{n-1},f_n) \\[6pt]&=\gcd(f_{m-n},f_n) \end{aligned} \] 观察可以发现这和 gcd 的形式相似，因此最终答案即为 \(f_{\gcd(n,m)}\) 。\(\square\)

然后就是矩阵快速幂了，不会可以去做一下 P1962 斐波那契数列。

时间复杂度 \(\mathcal{O}(\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector<int> vec;
typedef vector<vec> Mat;
const int P = 1e8;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
#define N ((int)())

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
Mat mul(Mat A, Mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    Mat C(n, vector<int>(p));
    for(int k = 0; k < m; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < p; j++)
                add(C[i][j], A[i][k] * B[k][j] % P);
    return C;
}
Mat qpow(Mat A, int k)
{
    int n = max(A.size(), A[0].size());
    Mat B(n, vector<int>(n));
    for(int i = 0; i < n; i++) B[i][i] = 1;
    while(k)
    {
        if(k & 1) B = mul(B, A);
        k >>= 1; A = mul(A, A);
    }
    return B;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; int d = gcd(n, m);
    if(d <= 2) return cout << "1\n", 0;
    Mat A(2, vector<int>(2)), B(2, vector<int>(1));
    A[0][0] = A[0][1] = A[1][0] = 1; B[0][0] = B[1][0] = 1;
    A = qpow(A, d - 2); A = mul(A, B); cout << A[0][0] << '\n';
    return 0;
}