CRTFun
SRM 193 · 2004-05-05 · by brett1479
SRM 193 · 2004-05-05 · by brett1479 · Brute Force, Simple Math
Problem Statement
Problem Statement
You will be given a int[] mods such that no two distinct elements of mods share a factor greater than 1. In other words, every pair of distinct elements will be relatively prime. Let P denote the product of the integers in mods. Someone has picked an integer between 0 and P-1 inclusive, but they won't tell you it. Instead they reveal what the number is mod k, for each k in mods. The ith element of vals will be the value of the picked number mod the ith element of mods. For example, if
mods = { 2, 3, 5, 7 }, and
vals = { 1, 2, 2, 5 },
then the number in question will satisfy the following congruences:
number mod 2 = 1 , number mod 3 = 2 , number mod 5 = 2 , and number mod 7 = 5 .Return the picked number. To simplify matters, the picked number will never be greater than 100000.
Notes
- The solution will always be unique.
Constraints
- mods will contain between 2 and 50 elements inclusive.
- Each element of mods will be between 2 and 100000 inclusive.
- Each element of mods will be distinct.
- No two distinct elements of mods will share a factor other than 1.
- vals will contain the same number of elements as mods.
- vals[i] is between 0 and mods[i]-1 inclusive.
- The picked number will be between 0 and 100000 inclusive.
- In addition, the picked number will be less than P, where P is the product of the elements in mods.
Examples
0)
{ 2, 3, 5, 7 }
{ 1, 2, 2, 5 }
Returns: 47
From above.
1)
{ 5, 13 }
{ 2, 3 }
Returns: 42
2)
{ 5 , 11 }
{ 4 , 5 }
Returns: 49
3)
{ 9, 8, 7 }
{ 1, 2, 3 }
Returns: 10
4)
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 0
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CRTFun with a public method int findSolution(vector<int> mods, vector<int> vals) · 78 test cases · 2 s / 256 MB per case