Remainder Fantasy
Statement
Goal
This was a puzzle invented and solved by Chinese during the 3rd to 5th centuries AD, with innovative solution steps recorded in Mathematical treaties of that era. Translated the text into modern terminologies:Let x be an integer. Divide x by 3, remains 2; divide x by 5, remains 3; divide x by 7, remains 2. Find the minimum value of x.
You are going to solve similar puzzles with the aid of state-of-the-art technologies and know-how. Take the challenge?
Beware, the moduli you are given may not be pairwise coprime. Moreover, your answer must always be as small as possible while being greater than or equal to every modulo in input. For instance, if you are asked for an integer x such that:
- it remains 3 when dividing x by 8
- it remains 11 when dividing x by 15
- it remains 1 when dividing x by 10,
then the answer is 131. In this example, 11 is not a valid answer since it is less than 15 (the modulo in the second constraint).
Input
Line 1: An integer N for the number of given conditions.
Next N lines: Two space separated integers m and r for the divisor and remainder of a condition where
x mod m = r
Next N lines: Two space separated integers m and r for the divisor and remainder of a condition where
x mod m = r
Output
Line 1 : The minimum value of x fulfilling all the given conditions, and at the same time x >= all of the given m.
Constraints
1 ≤ N ≤ 10
0 ≤ r
0 < x < 2 ^32
0 ≤ r
0 < x < 2 ^32
Example
Input
3 3 2 5 3 7 2
Output
23
Tags
Remainder Theorem, Arithmetic
Difficulty
Medium
Test cases
Simple Test
Input
3
3 2
5 3
7 2
Output
23
Validator 1 Validator
Input
3
3 2
5 4
7 3
Output
59
Warm Up Test
Input
4
5 1
7 2
9 3
11 4
Output
1731
Validator 2 Validator
Input
4
7 5
8 6
9 7
13 8
Output
502
Harder Test
Input
4
11 10
17 11
149 17
23 15
Output
353594
Validator 3 Validator
Input
4
47 17
271 181
17 15
223 222
Output
9217704
Get serious Test
Input
5
2 0
47 7
271 22
17 3
1619 913
Output
199022964
Validator 4 Validator
Input
4
191 3
239 14
241 39
353 4
Output
1687906922
Brute-force not work Test
Input
6
3 2
17 8
29 18
59 30
61 60
349 15
Output
1699580108
Validator 5 Validator
Input
6
7 2
17 7
31 6
47 5
61 3
197 193
Output
1171050736
Many Conditions Test
Input
9
2 1
5 3
7 2
11 1
13 3
17 1
19 4
23 1
29 1
Output
1780880663
Validator 6 Validator
Input
9
2 1
5 2
7 1
11 3
13 1
17 4
19 1
23 2
29 17
Output
1207575097
A Few Big Conditions Test
Input
3
9 1
9721 653
104677 11555
Output
2097947989
Validator 7 Validator
Input
3
11 9
9719 311
91367 515
Output
1266347135
Tricky Small Test
Input
3
6 1
16 1
5 1
Output
241
Validator 8 Validator
Input
5
2 1
3 1
4 1
5 1
6 1
Output
61
Nasty Big Test
Input
3
1473 1031
1234 1141
1827 50
Output
1024360583
Validator 9 Validator
Input
3
5454 1717
1199 1141
999 799
Output
88983727
Solution language
Solution
Stub generator input