相关链接
题目传送门：http://agc015.contest.atcoder.jp/tasks/agc015_f
解题报告
我们写出使答案最大且值最小的序列，不难发现这是一个斐波那契数列
进一步发现，这条主链的每一个点只会引申出一条支链，且支链不会再分
所以我们可以暴力算出了$\log n$条链，共$\log ^ 2 n$对数，然后暴力算贡献
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MOD = 1000000007;
const int LOG = 100;
vector<pair<LL, LL> > num[LOG];
inline LL read() {
char c = getchar(); LL ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}
inline void solve(LL A, LL B) {
if (A < num[2][0].first || B < num[2][0].second) {
printf("1 %d\n", A * B % MOD);
return;
}
for (int i = 2; i < LOG; i++) {
if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
int cnt = 0;
for (int j = 0; j < (int)num[i].size(); j++) {
LL a = num[i][j].first, b = num[i][j].second;
cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
}
printf("%d %d\n", i, cnt);
return;
}
}
}
inline void prework() {
num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < (int)num[i - 1].size(); ++j) {
LL a = num[i - 1][j].first, b = num[i - 1][j].second;
num[i].push_back(make_pair(b, a + b));
}
LL a = num[i - 1][0].first, b = num[i - 1][0].second;
num[i].push_back(make_pair(a + b, 2 * a + b));
}
}
int main() {
prework();
for (int T = read(); T; T--) {
LL A = read(), B = read();
solve(min(A, B), max(A, B));
}
return 0;
}