相关链接
题目传送门: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; }