Two coins
On an island only coins of two denominations circulate: a and b tenge. You buy something for c tenge and may give coins to the seller and receive coins as change; both of you have as many coins as needed. What is the smallest number of coins that will change hands, in both directions together?
In other words, integers x and y with a·x + b·y = c are needed (a positive number means coins from you, a negative one change to you), and among all such pairs the smallest |x| + |y|.
Input
The first line holds the number of purchases q (1 ≤ q ≤ 20,000). Each of the following lines holds a, b, c (1 ≤ a, b ≤ 10⁹, 0 ≤ c ≤ 10⁹).
Output
For each purchase, the smallest number of coins, or -1 if exactly c cannot be paid.
Examples
Example 1
6 3 5 4 4 6 7 5 5 10 7 3 0 1 1 1 2 7 1
4 -1 2 0 1 4
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 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
When is the equation a·x + b·y = c solvable in integers at all? Think about what the left-hand side is divisible by for any x and y.
2Hint 2
If one solution (x, y) has been found, how do you get all the others from it? Try adding something to x and taking something from y without changing the sum.
3The idea
The left-hand side is always divisible by g = gcd(a, b), so if c is not a multiple of g, the answer is −1. Otherwise the extended Euclidean algorithm gives a·x₀ + b·y₀ = g, and multiplying by c/g gives one solution. All solutions are x = x₀ + t·b/g, y = y₀ − t·a/g for integer t. It remains to choose the t for which |x| + |y| is smallest.
4Walkthrough
The function f(t) = |x₀ + t·B| + |y₀ − t·A|, where A = a/g and B = b/g, is a sum of two “V” shapes, that is, a convex broken line. Its minimum lies at a kink, and the kinks are where one of the brackets turns to zero: t = −x₀/B and t = y₀/A. These points are usually not integers, so check a few integer t near each and take the best.
In the first sample a = 3, b = 5, c = 4: the solutions 3·3 − 5·1 = 4 and 3·(−2) + 5·2 = 4 give four coins each, and fewer is impossible. This is the same problem as the famous puzzle of the two jugs of 3 and 5 litres: how to measure out exactly 4.
Be careful with rounding: in Go integer division rounds towards zero, while we need the floor. For negative numbers these differ, so the reference has its own floorDiv. The numbers fit in int64: |x₀| ≤ b/g, and after multiplying by c/g at most 10¹⁸.
4+Solution
5Complexity
O(log min(a, b)) for the extended algorithm and O(1) for trying the candidates. O(q log max(a, b)) in all.
6Common mistakes
- The first solution instead of the best. The coefficients of the extended algorithm, multiplied by c/g, can be huge: about 10¹⁸ coins instead of a dozen.
- Trying every x. Trying all x from −c to c is honest, but with c = 10⁹ it is a billion steps per purchase.
- Rounding towards zero.
-7 / 2in Go gives −3, while the floor is −4. Missing the right candidate gives an answer one or two worse.