Farhan's cryptography demo also needs the Chinese Remainder Theorem: given two modular constraints on an unknown number, find the smallest value satisfying both. Given two congruences X ≡ R1 (mod M1) and X ≡ R2 (mod M2) where M1 and M2 are coprime, find the smallest non-negative X satisfying both, modulo M1*M2.
Input
Four integers R1 M1 R2 M2.
Output
The smallest non-negative X (mod M1*M2) satisfying both congruences.
Constraints
0 ≤ R1<M1, 0 ≤ R2<M2 ≤ 10^6, gcd(M1,M2)=1
Sample Input
2 3 3 5
Sample Output
8
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.