agc015F - Kenus the Ancient Greek(结论题)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define Pair pair<LL, LL> 
#define MP(x, y) make_pair(x, y)
#define fi first 
#define se second 
#define LL long long 
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, B = 90, mod = 1e9 + 7;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
vector<Pair> v[B + 1];
LL f[B + 1];
void Pre() {
    f[0] = f[1] = 1;
    for(int i = 2; i <= B; i++) f[i] = f[i - 1] + f[i - 2];
    v[1].push_back(MP(1, 2)); v[1].push_back(MP(1, 3)); v[1].push_back(MP(1, 4));
    for(int i = 1; i <= B - 3; i++) {
        for(int j = 0; j < v[i].size(); j++) {
            LL x = v[i][j].fi, y = v[i][j].se;
            LL tmp = x; x = y; y = tmp + y;
            while(y <= f[i + 3] + f[i - 1]) v[i + 1].push_back(MP(x, y)), y += x;
        }
    }
}
main() {
    // freopen("1.in", "r", stdin);
    Pre();
    int Q = read();
    while(Q--) {
        LL x = read(), y = read(), K;
        if(x > y) swap(x, y);
        for(K = 1; f[K + 1] <= x && f[K + 2] <= y; K++);
        cout << K << " ";
        if(K == 1) {cout << x * y % mod << endl; continue;}
        LL ans = 0;
        for(int i = 0; i < v[K - 1].size(); i++) {
            LL a = v[K - 1][i].fi, b = v[K - 1][i].se;
        //    printf("%I64d %I64d\n", a, b);
            if(b <= x) ans += (y - a) / b % mod;
            if(b <= y) ans += (x - a) / b % mod;
            //if(a + b <= x && b <= y) ans++;
            //if(a + b <= y && a <= x) ans++;
            ans %= mod;
        }
        cout << ans % mod<< endl;
    }
    return 0;
}