请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)，答案对 \(10^8\) 取模。
结论：\(\gcd(f_n, f_m) = f_{\gcd(n, m)}\)
证明如下：
首先引理 1：
\[f_{n + m} = f_{n - 1} \times f_{m} + f_{n}\times f_{m + 1}
\]
运用归纳法，可以简单证明，此处略去。
引理 2：
\[\gcd(f_n, f_{n + 1}) = 1\\
\]
运用归纳法：
\(\gcd(f_1, f_{2}) = 1\) 平凡成立。
设现已有 \(\gcd(f_{n - 1}, f_n) = 1\)，则
\(\gcd(f_n, f_{n + 1}) =\gcd(f_n, f_{n - 1} + f_n) = \gcd(f_{n - 1}, f_n) = 1\)
证毕。
\[\begin{aligned}
由引理 1知，f_{m} =& f_{n - m - 1} f_{n} + f_{n - m} f_{n + 1}\\
\therefore \gcd(f_n, f_m) = &\gcd(f_n, f_{n - m - 1} f_{n} + f_{n - m} f_{n + 1})\\
\because f_n | f_{n - m - 1} f_{n}\\
\therefore \gcd(f_n, f_m) = &\gcd(f_n, f_{n - m} f_{n + 1})\\
由引理 2知，\gcd(f_n, f_{n + 1}) = 1\\
\therefore\gcd(f_n, f_m) = &\gcd(f_n, f_{n - m})\\
\gcd(f_n, f_m) = &\gcd(f_{n - m}, f_n)\\
\therefore \gcd(f_n, f_m) = &\gcd(f_{n\ \bmod\ m}, f_n)\\
如此递归，最后结果为 \gcd(f_n, f_m) = &\gcd(f_{\gcd(n, m)}, 0) = f_{\gcd(n, m)}\\
此处可类比欧几里得算法
\end{aligned}
\]
最后用矩阵算 \(f_{\gcd(n, m)}\) 即可。
#include <algorithm>
#include <cstring>
#include <iostream>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define int long long
using namespace std;
const int mod = 1e8;
struct Mat
{
int m[5][5];
int r, c;
void clear(int R, int C)
{
memset(m, 0, sizeof m);
r = R, c = C;
}
void init()
{
for (int i = 0; i <= min(r, c); i++)
m[i][i] = 1;
}
friend Mat operator*(const Mat a, const Mat b)
{
Mat res;
res.clear(a.r, b.c);
for (int i = 1; i <= a.r; i++)
for (int j = 1; j <= b.c; j++)
for (int k = 1; k <= a.c; k++)
res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
return res;
}
} M, A;
Mat qmi(Mat a, int b)
{
Mat res;
res.clear(3, 3), res.init();
while (b)
{
if (b & 1)
res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
signed main()
{
speedup;
int n, m;
cin >> n >> m;
M.clear(2, 2);
M.m[1][2] = M.m[2][1] = M.m[2][2] = 1;
A.clear(2, 1);
A.m[2][1] = 1;
A = qmi(M, __gcd(n, m) - 1) * A;
cout << A.m[2][1] << '\n';
return 0;
}