CRTFun | Topcoder Archive

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.

Definition

Class:: CRTFun
Method:: findSolution
Parameters:: int[], int[]
Returns:: int
Method signature:: int findSolution(int[] mods, int[] vals)
(be sure your method is public)

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

```
{ 2, 3, 5, 7 }
```
```
{ 1, 2, 2, 5 }
```
```
Returns: 47
```
From above.
```
{ 5, 13 }
```
```
{ 2, 3 }
```
```
Returns: 42
```
```
{ 5 , 11 }
```
```
{ 4 , 5 }
```
```
Returns: 49
```
```
{ 9, 8, 7 }
```
```
{ 1, 2, 3 }
```
```
Returns: 10
```

{343,1331,2197,4913,6859,12167,24389,29791,50653,68921,79507}

{221,1026,945,3903,3999,1793,13905,8503,38294,38294,38294}

Returns: 38294

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.