The hunting tooth
Two gears mesh: the first has a teeth, the second b. Mark with paint one tooth of the first gear and the one gap of the second that it has just entered. After how many full turns of each gear will this pair meet again?
Engineers like the tooth counts to be coprime: then every tooth of the first gear in time visits every gap of the second, and wear is spread evenly. Such a pair is called a gear with a “hunting tooth”. Determine this too for each pair of gears.
Input
The first line holds the number of pairs q (1 ≤ q ≤ 100,000). Each of the following q lines holds a and b (1 ≤ a, b ≤ 10¹⁸).
Output
For each pair, a line of four values: the greatest common divisor of a and b; how many turns the first gear makes before the pair meets again; how many the second makes; yes if the gear has a hunting tooth, otherwise no.
Examples
Example 1
5 40 15 41 15 12 12 1 7 89 55
5 3 8 no 1 15 41 yes 12 1 1 no 1 7 1 yes 1 55 89 yes
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
In one turn of the first gear, a teeth pass the point of mesh. The pair meets again when a number of teeth that is a multiple of both a and b has passed through the mesh. What is the smallest such number?
2The idea
The number of teeth needed is the least common multiple: lcm(a, b) = a·b / gcd(a, b). The first gear makes lcm / a = b / gcd turns, the second a / gcd. A gear with a hunting tooth means gcd = 1: then the first gear manages a full b turns, and its tooth visits all b gaps.
3Walkthrough
Compute the gcd by Euclid's algorithm with division with remainder and divide both numbers by it. The lcm itself need not be computed, which is lucky: with a, b up to 10¹⁸ it reaches 10³⁶ and does not fit in any integer type in Go. The answer is the quotients b/gcd and a/gcd, which are at most 10¹⁸.
In Go uint64 (and even int64) is enough for numbers up to 10¹⁸: the remainders only decrease, so overflow has nowhere to come from.
3+Solution
4Complexity
At most 85 divisions per pair (the worst case up to 10¹⁸ is neighbouring Fibonacci numbers, which are in the third test), O(q log max(a, b)) in all.
5Common mistakes
- Subtraction instead of division. Euclid in the Elements subtracted the smaller from the larger. On the pair (10¹⁸, 1) that is 10¹⁸ subtractions: the second test.
- The lcm through the product.
a * b / gin Go overflows long before 10¹⁸ × 10¹⁸. Divide first,a / g * b, and here the lcm is not needed at all. - Turns mixed up. The first gear makes b/gcd turns, not a/gcd: the gear with fewer teeth turns more often.