Two Remainder Conditions
Find the smallest POSITIVE integer x with x ≡ A (mod M) and x ≡ B (mod N), where M and N are coprime.
Input: one line with four integers A M B N (0 ≤ A < M, 0 ≤ B < N, gcd(M, N) = 1).
Output: the smallest positive solution.
Constraints:
- 2 ≤ M, N ≤ 106
- gcd(M, N) = 1
Sample Tests
Input 1
2 3 3 5
Output 1
8
Input 2
0 3 0 5
Output 2
15
Discussion (opens after you solve — no spoilers before)
No comments yet.