Submission #3226187
Source Code Expand
/*
结论题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)$,所以不成立
那么现在要做的就是求“优秀的”数对的个数。
考虑直接用欧几里得算法的定义递推即可
*/
#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;
}
/*
1
12 11
*/
Submission Info
Submission Time |
|
Task |
F - Kenus the Ancient Greek |
User |
attack |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
2550 Byte |
Status |
AC |
Exec Time |
1053 ms |
Memory |
4096 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1700 / 1700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
747 ms |
3328 KB |
02.txt |
AC |
751 ms |
3328 KB |
03.txt |
AC |
735 ms |
3328 KB |
04.txt |
AC |
752 ms |
3328 KB |
05.txt |
AC |
740 ms |
3328 KB |
06.txt |
AC |
734 ms |
3328 KB |
07.txt |
AC |
737 ms |
3328 KB |
08.txt |
AC |
734 ms |
3328 KB |
09.txt |
AC |
735 ms |
3328 KB |
10.txt |
AC |
743 ms |
3328 KB |
11.txt |
AC |
1049 ms |
1920 KB |
12.txt |
AC |
1053 ms |
1920 KB |
13.txt |
AC |
632 ms |
1920 KB |
14.txt |
AC |
627 ms |
1920 KB |
15.txt |
AC |
671 ms |
4096 KB |
16.txt |
AC |
702 ms |
4096 KB |
17.txt |
AC |
552 ms |
3840 KB |
18.txt |
AC |
567 ms |
3840 KB |
19.txt |
AC |
951 ms |
3584 KB |
20.txt |
AC |
969 ms |
3584 KB |
21.txt |
AC |
1 ms |
384 KB |
22.txt |
AC |
1 ms |
384 KB |
23.txt |
AC |
1 ms |
384 KB |
24.txt |
AC |
1 ms |
384 KB |
s1.txt |
AC |
1 ms |
384 KB |
s2.txt |
AC |
1 ms |
384 KB |