Chinese Remainder Theorem | Set 1 ( Introduction ) | A C ++ program to demonstrate working of Chinise remainder Theorem ; k is size of num [ ] and rem [ ] . Returns the smallest number x such that : x % num [ 0 ] = rem [ 0 ] , x % num [ 1 ] = rem [ 1 ] , ... ... ... ... ... ... x % num [ k - 2 ] = rem [ k - 1 ] Assumption : Numbers in num [ ] are pairwise coprime ( gcd for every pair is 1 ) ; As per the Chinese remainder theorem , this loop will always break . ; Check if remainder of x % num [ j ] is rem [ j ] or not ( for all j from 0 to k - 1 ) ; If all remainders matched , we found x ; Else try next number ; Driver method
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinX ( int num [ ] , int rem [ ] , int k ) { while ( true ) { int j ; for ( j = 0 ; j < k ; j ++ ) if ( x % num [ j ] != rem [ j ] ) break ; if ( j == k ) return x ; x ++ ; } return x ; } int main ( void ) { int num [ ] = { 3 , 4 , 5 } ; int rem [ ] = { 2 , 3 , 1 } ; int k = sizeof ( num ) / sizeof ( num [ 0 ] ) ; cout << " x ▁ is ▁ " << findMinX ( num , rem , k ) ; return 0 ; }