定義一數列$F$為：
$F_1=1, F_2=2$。
$F_n=F_n-1+F_n-2$。
給定兩正整數$a, b$，求$gcd(F_a, F_b)$
$a, b\le 10^{18}$
$F$其實就是費式數列，只是被位移了一格
先讓他變回正常的費式數列$f(f_1=1,f_2=1)$，此時$F_n=f_{n+1}$。
然後費式數列有個性質:
$$gcd(f_n, f_m)=f_{gcd(n, m)}$$
推導過程需要用蠻多其他定理的，
總之，這樣就等同於求數列某項，直接矩陣快速冪就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const int MOD = 1e9+7;
using mat = vector<vector<ll>>;
mat operator*(mat &a, mat &b) {
mat res(2, vector<ll>(2));
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD;
return res;
}
int get(ll n) {
mat a = {{1, 1}, {1, 0}}, res = {{1, 0}, {0, 1}};
for(; n; n>>=1, a = a * a)
if(n & 1)
res = res * a;
return res[1][0];
}
signed main() {
EmiliaMyWife
ll n, m;
cin >> n >> m;
cout << get(__gcd(n + 1, m + 1)) << '\n';
return 0;
}
|