中国剩余定理——解决对非质数的取余问题

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=107;
int m[N];// 质除数
int p[N];// 余数
int e_gcd (int a,int b,int &x,int &y) {
    if (b==0) {
        x=1;
        y=0;
        return a;
    }                      // a*x1+b*y1=1;
                           // a*y2+b*(x2-(a/b)*y2)=1 
    int d=e_gcd (b,a%b,y,x);// 作用 ：求出x2与y2 并且使y1=x2; x1=y2;
    y=y-(a/b)*x;//y1=x2-(a/b)*y2;
    return d;
}
int china (int m[],int p[],int n) {
    int M=1;
    for (int i=1;i<=n;i++)
        M=M*m[i];
    int ans=0;
    for (int i=1;i<=n;i++) {
        int a=M/m[i];
        int x,y;
        e_gcd (a,m[i],x,y);
        x=x*p[i]*a;//important!!!
        ans+=(x+M)%M;
    }
    return ans%M;
}
int main ()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>m[i]>>p[i];
    }
    int ans=china (m,p,n);
    cout<<ans<<endl;
    return 0;
}