分类：最大公约数与最小公倍数

最小公倍数。

这题应该算是经典模型了。

如果模拟一下变换过程，可以发现：

1. 所有的数的行进路线都会是一个闭合的环。
2. 同一个环上的数总是同时恢复到原始状态。
3. 一个数恢复到原始状态所需次数为这个数所在环的长度。
4. 不同的环之间相互独立。

那么显然（参见小学奥数），要使所有数恢复到原始状态，所需次数即为所有数最小移动次数的最小公倍数，即为所有环长度的最小公倍数。

注意：这题如果直接用 lcm(a, b) = a * b / gcd(a, b) 会超出 long long 范围，所以计算过程应采用分解质因数或求乘法逆元。

代码如下（分解质因数）：

继续阅读[FJOI WC 2017] geronimo

对于 Fibonacci 数列 {Fi} 存在这样一个定理：

那么题意可以转化为求 Fibonacci 数列的第 gcd(n, m) 项对 1000000007 取模的值。

注意这个数可能会达到 10^18，故使用矩阵乘法优化计算。

Reference:

斐波那契数列 - 维基百科，自由的百科全书

代码如下：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>



using namespace std;



inline void set_file_IO(string);

inline void close_IO(void);

inline void work(void);



int main(void) {

    #ifndef ONLINE_JUDGE

        set_file_IO("sequence");

    #endif

    ios::sync_with_stdio(false);

    work();

    #ifndef ONLINE_JUDGE

        close_IO();

    #endif

    return 0;

}



typedef long long ll;



const ll Mod = 1000000007;



template<int Size>



struct matrix {

    ll data[Size][Size];

    

    matrix() {

        memset(data, 0, sizeof data);

    }

    

    matrix<Size> operator *(const matrix<Size> b) {

        matrix<Size> res;

        for (int i=0; i<Size; ++i) {

            for (int j=0; j<Size; ++j) {

                for (int k=0; k<Size; ++k) {

                    (res.data[i][j] += data[i][k] * b.data[k][j]) %= Mod;

                }

            }

        }

        return res;

    }

    

    void operator *= (const matrix<Size> b) {

        *this = *this * b;

    }

    

    matrix<Size> operator ^(ll exp) {

        matrix<Size> res;

        for (int i=0; i<Size; ++i) {

            res.data[i][i] = 1;

        }

        for (matrix<Size> base=*this; exp; base*=base, exp>>=1LL) {

            if (exp & 1LL) {

                res *= base;

            }

        }

        return res;

    }

    

    matrix operator ^=(const ll exp) {

        return *this = *this ^ exp;

    }

};



inline void single(void) {

    ll n, m;

    cin >> n >> m;

    while (m) {

        const ll t = m;

        m = n % m;

        n = t;

    }

    

    matrix<2> ans, ast;

    ans.data[0][1] = 1;

    ast.data[0][0] = ast.data[0][1] = ast.data[1][0] = 1;

    ans *= ast ^= n;

    cout << ans.data[0][0] << endl;

}



/*

                 1          ,  1



                 1          ,  0



f[i], f[i-1]     f[i]+f[i-1],  f[i]



0   , 0          0          ,  0

*/



inline void work(void) {

    int T;

    cin >> T;

    while (T--) {

        single();

    }

}



inline void set_file_IO(string name) {

    freopen((name + ".in" ).c_str(), "r", stdin );

    freopen((name + ".out").c_str(), "w", stdout);

}



inline void close_IO(void) {

    fclose(stdin);

    fclose(stdout);

}