Redirecting to

Chinese Remainder Theorem

We are given a set of congruence equations.
a = a1 (mod n1)
a = a2 (mod n2)

Where ai are some given constants, which indicates ai = a % ni.
The original form of CRT(Chinese Remainder Theorem) states that the given set of congruence equations always has one and exactly one solution modulo m. where m = lcm(n1, n2).

Find exactly one value of a.
If it's not possible to find the value of a then print "no solution";
Input Format
The first line of input consists of four integers a1, n1, a2, n2.
Output Format
Print two integers a, M, where M = lcm(n1, n2) and 0 <= a < M, giving the solution a (mod M) to the equations
a = a1 (mod n1)
a = a2 (mod n2)
Print "no solution" if there is no solution for a given set of congruence equations;
Question Video
1 <= n1, n2 <= 10^9
0 <= a1 < n1
0 <= a2 < n2
Sample Input
10000 23000 10000 23000
Sample Output
10000 23000

  • Asked in Companies
  • Related Topics

Video Solution

Code Solution

Id Name