中国剩余定理

sakuya726 · 2018-11-04 09:58:21 · 个人记录

#include<bits/stdc++.h>
using namespace std;
#define rg register
int n,prime[15],r[15];
inline int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int temp=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return temp;
}
inline int China(int len)
{
    int n=1,m,sum,x,y,d;
    for(rg int i=1;i<=len;++i)
    {
        n*=prime[i];
    }
    for(rg int i=1;i<=len;++i)
    {
        m=n/prime[i];
        d=exgcd(prime[i],m,x,y);
        sum=(sum+y*m*r[i])%n;   
    }
    return (n+sum%n)%n;
}
int main()
{
    while(~scanf("%d",&n))//输入n组数据 
    {
        for(rg int i=1;i<=n;++i)//求一个数x 满足x%(prime[1...n]=r[1...n] 
        {
            cin>>prime[i]>>r[i];
        }
        cout<<China(n)<<endl;
    }   
}