#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; }
中国剩余定理和扩展欧几里得定理