Chinese Remainder (Two)
Hard
Computer Mathematics
Modular Arithmetic
28 views
Problem Statement
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.
Example
2 3 3 5
8
Constraints
m,n coprime
Input / Output Format
Input Format
Four integers a m b n.
Output Format
One integer smallest x.
Constraints
m,n coprime
Examples
Input:
2 3 3 5
Output:
8
Example Solution (Public)
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).
Official Solution Code
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).
Please login to submit solutions.