题意
$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 %i64dn", 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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607753.html