Two Remainder Conditions — Solution & Editorial

Back to the Problem

Chinese Remainder: x = A + M·k where k ≡ (B−A)·M⁻¹ (mod N); the inverse exists by coprimality. If the result is 0, the smallest positive is MN.

Complexity: O(log)

Watch out: A = B = 0 makes x = 0 — the smallest POSITIVE answer is then M·N.