中国剩余定理 12@亿万星辰

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
int ex_gcd(int a,int b,int &x,int &y)//扩展欧几里得定理 
{
	int d;
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	d=ex_gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int Chinese_Remainder(int a[],int prime[],int len)//中国剩余定理 
{
	int m=1,M,R,y,d,sum=0;
	for(int i=1;i<=len;i++) m*=prime[i];
	for(int i=1;i<=len;i++){
		M=m/prime[i];
		d=ex_gcd(M,prime[i],R,y);//求出最大公约数和a的逆元R 
		sum=(sum+a[i]*M*R)%m;//求∑(Rj*Mj)*aj  %m 
	}
	return (m+sum%m)%m;
} 
int main()
{
	int a[MAX],m[MAX],ant=0,x,b,d;
	while(scanf("%d",&b)!=0&&scanf("%d",&d)!=0&&b!=0){//赋值输入0 0时结束 
		++ant;
		a[ant]=d,m[ant]=b;
	}
	x=Chinese_Remainder(a,m,ant);
	printf("%d\n",x);
	return 0;
}