{"id":"9c9dcea8-2d47-4017-8466-b5f635f09eac","name":"Chinese Remainder Theorem","description":"We are given a set of congruence equations.\r\na = a1 (mod n1)\r\na = a2 (mod n2)\r\n\r\nWhere ai are some given constants, which indicates ai = a % ni. \r\nThe 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).\r\n\r\nFind exactly one value of a.\r\nIf it's not possible to find the value of a then print \"no solution\";","inputFormat":"The first line of input consists of four integers a1, n1, a2, n2.","outputFormat":"Print two integers a, M, where M = lcm(n1, n2) and 0 <= a < M, giving the solution a (mod M) to the equations\r\na = a1 (mod n1)\r\na = a2 (mod n2)\r\nPrint \"no solution\" if there is no solution for a given set of congruence equations;","constraints":"1 &lt;= n1, n2 &lt;= 10^9\r\n0 &lt;= a1 &lt; n1\r\n0 &lt;= a2 &lt; n2","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static void main(String[] args) {\r\n //Write code here\r\n\r\n\r\n }\r\n\r\n//========= Extended Euclidean Algorithm =========//\r\n//------------------------------------------------//\r\n\r\n public static class Pair {\r\n long x;\r\n long y;\r\n long gcd;\r\n\r\n public Pair(long x, long y, long gcd) {\r\n this.x = x;\r\n this.y = y;\r\n this.gcd = gcd;\r\n }\r\n }\r\n\r\n public static Pair euclids(long a, long b) {\r\n if (b == 0) {\r\n return new Pair(1, 0, a);\r\n }\r\n Pair dash = euclids(b, a % b);\r\n\r\n return new Pair(dash.y, dash.x - ((a / b) * dash.y), dash.gcd);\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"10000 23000 10000 23000","sampleOutput":"10000 23000\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"11157595-ef8a-4538-aecc-f56d867ec34e","name":"Chinese Remainder Theorem","slug":"chinese-remainder-theorem","type":1}],"next":{"id":"d17ab8a5-73cd-4d26-9155-82674f8c9cd7","name":"Monkey Tradition","type":1,"slug":"monkey-tradition"},"prev":{"id":"b3bdd6a6-75eb-452b-bb32-135945f99b12","name":"Sum Of Factors","type":1,"slug":"sum-of-factors"}}}

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";

{"id":"9c9dcea8-2d47-4017-8466-b5f635f09eac","name":"Chinese Remainder Theorem","description":"We are given a set of congruence equations.\r\na = a1 (mod n1)\r\na = a2 (mod n2)\r\n\r\nWhere ai are some given constants, which indicates ai = a % ni. \r\nThe 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).\r\n\r\nFind exactly one value of a.\r\nIf it's not possible to find the value of a then print \"no solution\";","inputFormat":"The first line of input consists of four integers a1, n1, a2, n2.","outputFormat":"Print two integers a, M, where M = lcm(n1, n2) and 0 <= a < M, giving the solution a (mod M) to the equations\r\na = a1 (mod n1)\r\na = a2 (mod n2)\r\nPrint \"no solution\" if there is no solution for a given set of congruence equations;","constraints":"1 &lt;= n1, n2 &lt;= 10^9\r\n0 &lt;= a1 &lt; n1\r\n0 &lt;= a2 &lt; n2","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static void main(String[] args) {\r\n //Write code here\r\n\r\n\r\n }\r\n\r\n//========= Extended Euclidean Algorithm =========//\r\n//------------------------------------------------//\r\n\r\n public static class Pair {\r\n long x;\r\n long y;\r\n long gcd;\r\n\r\n public Pair(long x, long y, long gcd) {\r\n this.x = x;\r\n this.y = y;\r\n this.gcd = gcd;\r\n }\r\n }\r\n\r\n public static Pair euclids(long a, long b) {\r\n if (b == 0) {\r\n return new Pair(1, 0, a);\r\n }\r\n Pair dash = euclids(b, a % b);\r\n\r\n return new Pair(dash.y, dash.x - ((a / b) * dash.y), dash.gcd);\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"10000 23000 10000 23000","sampleOutput":"10000 23000\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"11157595-ef8a-4538-aecc-f56d867ec34e","name":"Chinese Remainder Theorem","slug":"chinese-remainder-theorem","type":1}],"next":{"id":"d17ab8a5-73cd-4d26-9155-82674f8c9cd7","name":"Monkey Tradition","type":1,"slug":"monkey-tradition"},"prev":{"id":"b3bdd6a6-75eb-452b-bb32-135945f99b12","name":"Sum Of Factors","type":1,"slug":"sum-of-factors"}}}
plane

Editor

Loading...

Chinese Remainder Theorem

easy

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";

Constraints

1 <= n1, n2 <= 10^9 0 <= a1 < n1 0 <= a2 < n2

Format

Input

The first line of input consists of four integers a1, n1, a2, n2.

Output

Print two integers a, M, where M = lcm(n1, n2) and 0

Example

Sample Input

10000 23000 10000 23000

Sample Output

10000 23000

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode