1338. Solve ax + by = c In Integers
Find integers x and y with a*x + b*y = c, or report that none exist.
Print none if there is no solution. Otherwise print the solution with the
SMALLEST NON-NEGATIVE x, then its y. There are infinitely many solutions, so
that rule is what makes the answer unique.
The existence test is short and is the whole insight. Every value of a*x + b*y
is a multiple of gcd(a, b), so a solution exists exactly when gcd(a, b)
divides c. Nothing else can fail.
To build one, the extended Euclidean algorithm gives x0 and y0 with
a*x0 + b*y0 = gcd(a, b). Scaling both by c / gcd(a, b) solves the original.
That solution is rarely the one asked for. Every solution has the shape:
x = x0 + k * (b / g) y = y0 - k * (a / g) for any integer k
so shift x by whole multiples of b / g until it lands in 0 .. b/g - 1, then
compute the matching y from the equation directly.
Scaling can produce values far outside the inputs, so keep everything in 64-bit
integers even though a, b and c are small.
Constraints - `1 ≤ a, b ≤ 1000000` - `0 ≤ c ≤ 1000000000`
Input
One line containing three integers a, b and c.
Output
Print none if there is no integer solution. Otherwise print two integers separated by a space: the solution with the smallest non-negative x, then its y.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.