对于 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);
} |