Chinese Remainder (Two)
Computer Mathematics
Hard
2 views
Problem Description
Solve x ≡ a (mod m), x ≡ b (mod n) when m and n are coprime.
Input Format
Four integers a m b n.
Output Format
One integer smallest x.
Official Solution
Use CRT: find inv of m mod n, t=((b-a) mod n)*inv mod n, x=a+m*t, then mod lcm(m,n).
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!