1337. One Value, Two Remainders
Find the smallest non-negative x with:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
Print it, or -1 if no such x exists. The moduli are NOT guaranteed coprime.
Scanning candidates is O(n1 * n2) and hopeless at 10^9.
Write the first condition as x = a1 + n1 * t for some integer t. Substituting
into the second gives a1 + n1 * t ≡ a2 (mod n2), which is:
n1 * t ≡ (a2 - a1) (mod n2)
a single congruence in t. With g = gcd(n1, n2), that has a solution exactly
when g divides a2 - a1, and otherwise nothing works and the answer is -1.
When it does divide, cancel g throughout and the reduced coefficient is
invertible modulo n2 / g, so problem 1327 finishes it. Substituting t back
gives x, reduced modulo the least common multiple of the two moduli, which is
the period of the combined condition.
Most descriptions of this result assume coprime moduli, and the -1 case
disappears entirely under that assumption. Here it is half the problem, which is
why x ≡ 1 (mod 2) together with x ≡ 0 (mod 2) is in the tests.
Constraints - `2 ≤ n1, n2 ≤ 1000000000` - `0 ≤ a1 < n1` - `0 ≤ a2 < n2` - The least common multiple of `n1` and `n2` fits in a signed 64-bit integer.
Input
One line containing four integers a1, n1, a2 and n2.
Output
Print the smallest non-negative x satisfying both congruences, or -1 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.