洛谷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;
}