【模板】扩展中国剩余定理

佚名 6年前 (2019-04-19) 随笔 1277人围观抢沙发百度已收录

代码如下

#include <cstdio>
using namespace std;
typedef long long ll;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b)return x=1,y=0,a;
    ll d=exgcd(b,a%b,x,y),z=x;
    x=y,y=z-a/b*y;
    return d;
}
ll mul(ll a,ll b,ll p){
    ll ret=0;
    for(;b;b>>=1,a=(a+a)%p)if(b&1)ret=(ret+a)%p;
    return ret;
}

int n;ll ans,M,m,a,s,t;

void excrt(){
    scanf("%lld%lld",&M,&ans);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&m,&a);
        ll c=((a-ans)%m+m)%m;
        ll d=exgcd(M,m,s,t);
        s=mul(s,c/d,m/d);
        ans+=s*M;
        M=m/d*M;
        ans=(ans%M+M)%M;
    }
    printf("%lld\n",ans);
}

int main(){
    scanf("%d",&n);
    excrt();
    return 0;
}