-
Notifications
You must be signed in to change notification settings - Fork 364
/
Chinese_remainder.cpp
61 lines (51 loc) · 1.85 KB
/
Chinese_remainder.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*-----------------------------------------------------Introduction------------------------------------------------------------------------*/
/*The Chinese Remainder Theorem is used to solve modular arithmetic problems efficiently.Modular arithmetic involves performing
arithmetic operations on remainders. For example, if we divide 13 by 5, the remainder is 3. In modular arithmetic notation, we
would write this as 13 ≡ 3 (mod 5), which means that 13 is congruent to 3 modulo 5.*/
/*-----------------------------------------------------Algorithm----------------------------------------------------------------------------*/
/*start with 1 and one by one increment it and check if dividing it with given elements in
num[] produces corresponding remainders in rem[]. Once we find such an x, we return it. */
#include <iostream>
using namespace std;
// Function to find the smallest no that will produce respective remainder.
int findMinX(int num[], int rem[], int k)
{
int x = 1; // Initialize result
while (true)
{
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j=0; j<k; j++ )
if (x%num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
return x;
}
// Driver method
int main(void)
{
int num[100];
int rem[100];
int n = 0;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter elements of num array: ";
for (int i = 0; i < n; i++)
{
cin >> num[i];
}
cout << "Enter elements of rem array: ";
for (int i = 0; i < n; i++)
{
cin >> rem[i];
}
int k = n;
cout << "x is " << findMinX(num, rem, k) << endl;
return 0;
}