Submission #2237863
Source Code Expand
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> PI; namespace io { const int maxb = 1<< 15; char b[maxb], *s = b, *t = b; bool Getchar(char &ch) { return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++; } } LL Getint() { using namespace io; char ch; while (Getchar(ch) && (ch < '0' || ch > '9')); LL s = ch - '0'; while (Getchar(ch) && ch >= '0' && ch <= '9') s = s * 10 + ch - '0'; return s; } const LL INF = 1e18; const int maxn = 100; const int Mod = 1e9 + 7; void Chkadd(int &x, const int &y) { if ((x += y) >= Mod) x -= Mod; } int n; LL fib[maxn]; vector<PI> exc[maxn]; #define fir first #define sec second void Prepare() { fib[0] = fib[1] = 1; for (n = 1; fib[n] <= INF; ++ n) fib[n + 1] = fib[n] + fib[n - 1]; n -= 2; exc[1].push_back(PI(1, 2)); exc[1].push_back(PI(1, 3)); for (int i = 2; i <= n; ++ i) { vector<PI> &lst = exc[i - 1], &cur = exc[i]; int size = lst.size(); for (int j = 0; j < size; ++ j) { LL x = lst[j].fir, y = lst[j].sec; for (LL z = x + y; z <= fib[i + 2]; z += y) cur.push_back(PI(y, z)); } } } void Doit() { LL X = Getint(), Y = Getint(); if (X > Y) swap(X, Y); int k; for (k = 1; fib[k] <= X && fib[k + 1] <= Y; ++ k); -- k; if (k <= 1) { printf("1 "); if (X == 1) printf("%lld\n", Y % Mod); else puts("4"); return; } printf("%d ", k); vector<PI> &cur = exc[k - 1]; int size = cur.size(), ans = 0; for (int i = 0; i < size; ++ i) { LL x = cur[i].fir, y = cur[i].sec; if (X < y || Y < x + y) continue; Chkadd(ans, (Y - x) / y % Mod); if (X < x + y) continue; Chkadd(ans, (X - x) / y % Mod); } printf("%d\n", ans); return; } int main() { Prepare(); int Q = Getint(); while (Q --) Doit(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Kenus the Ancient Greek |
User | survivor |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 1921 Byte |
Status | AC |
Exec Time | 292 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 | 152 ms | 3328 KB |
02.txt | AC | 152 ms | 3328 KB |
03.txt | AC | 152 ms | 3328 KB |
04.txt | AC | 152 ms | 3328 KB |
05.txt | AC | 152 ms | 3328 KB |
06.txt | AC | 153 ms | 3328 KB |
07.txt | AC | 152 ms | 3328 KB |
08.txt | AC | 152 ms | 3328 KB |
09.txt | AC | 152 ms | 3328 KB |
10.txt | AC | 152 ms | 3328 KB |
11.txt | AC | 203 ms | 1920 KB |
12.txt | AC | 203 ms | 1920 KB |
13.txt | AC | 97 ms | 1920 KB |
14.txt | AC | 97 ms | 1920 KB |
15.txt | AC | 115 ms | 4096 KB |
16.txt | AC | 115 ms | 4096 KB |
17.txt | AC | 82 ms | 3840 KB |
18.txt | AC | 82 ms | 3840 KB |
19.txt | AC | 292 ms | 3584 KB |
20.txt | AC | 292 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 |