agc015F - Kenus the Ancient Greek(结论题)

题意

题目链接

$Q$组询问，每次给出$[x, y]$，定义$f(x, y)$为计算$(x, y)$的最大公约数需要的步数，设$i \leqslant x, j \leqslant y$，求$max(f(i, j))$，以及$max(f(i, j))$不同的数对$(i, j)$的个数

Sol

结论题Orz

设$f(x, y)$表示$(x, y)$辗转相除需要的步数，$fib(i)$表示第$i$个斐波那契数

常识：$f(fib[i], fib[i+1]) = i$。

定义一个数对是“好的”，当且仅当对于$(x, y)$，不存在更小的$x', y'$使得$f(x', y') > f(x, y)$

显然我们需要统计的数对一定是好的数对

定义一个数对是“优秀的”，当且仅当对于$(x, y)$，若$f(x, y) = k$, 满足$x, y \leqslant fib[k+2] + fib[k-1]$

结论！：一个好的数对辗转相除一次后一定是优秀的数对！

证明可以用反证法，也就是我先假设一个$f(a, b) = i$是好的，但是得到的数对$(x, y)$满足$y > fib[k+2] + fib[k-1]$

但是这样我们会得到一个$x' = f[i+2], y' = f[i+2]$满足$f(x', y')>f(a, b)$，所以不成立

那么现在要做的就是求“优秀的”数对的个数。

考虑直接用欧几里得算法的定义递推即可

不过代码是真·难写啊，去网上copy一份吧。。。

#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 + , B = , mod = 1e9 + ;

inline LL read() {

    char c = getchar(); LL x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

vector<Pair> v[B + ];

LL f[B + ];

void Pre() {

    f[] = f[] = ;

    for(int i = ; i <= B; i++) f[i] = f[i - ] + f[i - ];

    v[].push_back(MP(, )); v[].push_back(MP(, )); v[].push_back(MP(, ));

    for(int i = ; i <= B - ; i++) {

        for(int j = ; 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 + ] + f[i - ]) v[i + ].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 = ; f[K + ] <= x && f[K + ] <= y; K++);

        cout << K << " ";

        if(K == ) {cout << x * y % mod << endl; continue;}

        LL ans = ;

        for(int i = ; i < v[K - ].size(); i++) {

            LL a = v[K - ][i].fi, b = v[K - ][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 ;

}