gcd(fib[i],fib[j]) = fib[gcd(i,j)];
太6了
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<string>
5 #include<cmath>
6 #include<cstdio>
7 #include<iomanip>
8
9 #define ll long long
10
11 using namespace std;
12
13 const int mod = 1e8;
14
15 ll a, b;
16
17 ll base[3][3];
18 ll res[2][2];
19 ll tmp[3][3];
20
21 void base_upd()
22 {
23 for(int i = 1 ; i <= 2 ; i++){
24 for(int j = 1 ; j <= 2 ; j++){
25 for(int k = 1 ; k <= 2 ; k++){
26 tmp[i][j] += base[i][k] * base[k][j] % mod;
27 //tmp[i][j] %= mod;
28 }
29 }
30 }
31
32 for(int i = 1 ; i <= 2 ; i++){
33 for(int j = 1 ; j <= 2 ; j++){
34 base[i][j] = tmp[i][j] % mod;
35 }
36 }
37
38 tmp[1][1] = tmp[1][2] = tmp[2][1] = tmp[2][2] = 0;
39 }
40
41 void res_upd()
42 {
43 for(int j = 1 ; j <= 2 ; j++){
44 for(int k = 1 ; k <= 2 ; k++){
45 tmp[1][j] += base[k][j] * res[1][k] % mod;
46 //base[1][j] %= mod;
47 }
48 }
49
50 for(int j = 1 ; j <= 2 ; j++){
51 res[1][j] = tmp[1][j] % mod;
52 }
53
54 tmp[1][1] = tmp[1][2] = tmp[2][1] = tmp[2][2] = 0;
55 }
56
57 void matrix_ksm(ll k)
58 {
59 while(k)
60 {
61 if(k & 1){
62 res_upd();
63 }
64 base_upd();
65
66 k >>= 1;
67 }
68 }
69
70 ll solve(ll x)
71 {
72 base[1][1] = base[1][2] = base[2][1] = 1;
73 res[1][1] = res[1][2] = 1;
74
75 ll ans;
76
77 if(x == 1 || x == 2){
78 ans = 1;
79 }else{
80 matrix_ksm(x - 2);
81 ans = res[1][1];
82 }
83
84 return ans;
85 }
86
87 int main(){
88
89 cin >> a >> b;
90
91 ll k = __gcd(a, b);
92
93 cout << solve(k) << endl;
94
95 return 0;
96 }