当前位置： 移动技术网 > IT编程>开发语言>C/C++ > agc015F - Kenus the Ancient Greek(结论题)

agc015F - Kenus the Ancient Greek(结论题)

2018年09月21日  | 移动技术网IT编程  | 我要评论

2012展会信息,华聚网,李智雅整容

题意

$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 + 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;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网