중국 잉여정리

int		//  ax + by = gcd(a,b) = r .
Extend_Gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1; y = 0;
return	a;
}
else {
int r = Extend_Gcd(b, a%b, y, x);// r。
y -= a / b*x;
return	r;
}
}

int		// （ ）Chinese remainder
Crt(int a[], int m[], int n ){
int M = 1;
for (int i = 0; i < n; ++i )
M *= m[i];
int ans = 0;
for (int i = 0; i < n; ++i){
int x, y;
int tm = M / m[i];
Extend_Gcd( tm, m[i], x, y);
ans = (ans + tm * x * a[i]) % M;
}
return (ans + M) % M;
}

실전 훈련:
UVA, 756 BiorhythmsUVA 원본 링크
본교 ACM 링크
AC 코드, 주의, 끝에 함정이res

#include 
#define ll long long
int const N = 3;
ll	a[N], m[N] = { 23,28,33 }, Lcm, D;

//  ax + by = gcd(a,b) = r .
void gcd(ll a, ll b, ll &d, ll &x, ll &y ){
	if ( !b ) {
		d = a;
		x = 1, y = 0;
	}
	else {
		gcd( b, a%b, d, y, x );
		y -= (a / b)*x;
	}
}
// （ ）Chinese remainder
ll China(int n, ll *m, ll *a){
	ll M = 1, d, y, x = 0;
	for (int i = 0; i