Submission #1314305
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.StringTokenizer; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskF solver = new TaskF(); int testCount = Integer.parseInt(in.next()); for (int i = 1; i <= testCount; i++) solver.solve(i, in, out); out.close(); } static class TaskF { long x; long y; long[][] twooneprods; long[][] oneoneprods; static final long MODULO = (long) (1e9 + 7); public TaskF() { twooneprods = new long[87][4]; oneoneprods = new long[86][4]; long[] one = new long[]{0, 1, 1, 1}; long[] two = new long[]{0, 1, 1, 2}; for (int i = 0; i < twooneprods.length; ++i) { if (i > 0) { two = mul(one, two); } twooneprods[i] = two; } long[] p = new long[]{1, 0, 0, 1}; for (int i = 0; i < oneoneprods.length; ++i) { if (i > 0) { p = mul(one, p); } oneoneprods[i] = p; } } long[] mul(long[] a, long[] b) { long[] c = new long[4]; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { c[i * 2 + j] += a[i * 2 + k] * b[k * 2 + j]; } } } return c; } public void solve(int testNumber, InputReader in, PrintWriter out) { x = in.nextLong(); y = in.nextLong(); if (x > y) { long t = x; x = y; y = t; } long p = 0; long q = 1; int steps = 0; long ways = 0; while (true) { int t = (p == 0) ? 2 : 1; long np = q; long nq = p + t * q; if (np > x || nq > y) { if (q <= x) { ways = 2; } else { ways = 1; } break; } ++steps; p = np; q = nq; } if (steps <= 1) { steps = 1; ways = x % MODULO * (y % MODULO) % MODULO; } else { p = 0; q = 1; for (int i = 0; i < steps; ++i) { long mint = (p == 0) ? 2 : 1; long[] extra = oneoneprods[steps - 1 - i]; long c = q * extra[1]; long d = q * extra[0] + p * extra[1]; // c * t + d <= x long maxt = c == 0 ? Long.MAX_VALUE : (x - d) / c; long a = q * extra[3]; long b = q * extra[2] + p * extra[3]; // a * t + b <= y maxt = Math.min(maxt, (y - b) / a); if (i == steps - 1) { ways += maxt - mint; ways %= MODULO; } else { for (long t = mint + 1; t <= maxt; ++t) { long v1 = c * t + d; long v2 = a * t + b; ways += (y - v2) / v1 + 1; ways %= MODULO; } } if (a * mint + b <= x) { maxt = Math.min(maxt, (x - b) / a); ways += maxt - mint; ways %= MODULO; } long np = q; long nq = p + mint * q; if (np > x || nq > y) throw new RuntimeException(); p = np; q = nq; } ways %= MODULO; } out.println(steps + " " + ways); /*Pair p = rec(0, 1, -1); out.println(p.steps + " " + p.ways);*/ } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public long nextLong() { return Long.parseLong(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Kenus the Ancient Greek |
User | Petr |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1700 |
Code Size | 5592 Byte |
Status | AC |
Exec Time | 1481 ms |
Memory | 71428 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 | 867 ms | 45700 KB |
02.txt | AC | 867 ms | 46864 KB |
03.txt | AC | 1481 ms | 48672 KB |
04.txt | AC | 996 ms | 57908 KB |
05.txt | AC | 847 ms | 47364 KB |
06.txt | AC | 793 ms | 46888 KB |
07.txt | AC | 979 ms | 56112 KB |
08.txt | AC | 878 ms | 45336 KB |
09.txt | AC | 892 ms | 47744 KB |
10.txt | AC | 842 ms | 46260 KB |
11.txt | AC | 1349 ms | 47180 KB |
12.txt | AC | 1468 ms | 55700 KB |
13.txt | AC | 972 ms | 55580 KB |
14.txt | AC | 931 ms | 54380 KB |
15.txt | AC | 1050 ms | 56828 KB |
16.txt | AC | 942 ms | 54204 KB |
17.txt | AC | 530 ms | 66324 KB |
18.txt | AC | 646 ms | 71428 KB |
19.txt | AC | 1297 ms | 46328 KB |
20.txt | AC | 1225 ms | 47084 KB |
21.txt | AC | 71 ms | 21588 KB |
22.txt | AC | 70 ms | 19412 KB |
23.txt | AC | 72 ms | 21332 KB |
24.txt | AC | 68 ms | 21460 KB |
s1.txt | AC | 68 ms | 17876 KB |
s2.txt | AC | 71 ms | 19156 KB |