洛谷P4777 【模板】擴展中國剩余定理（EXCRT）

傳送門

?

關于excrt

//minamoto
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=1e5+5;
int n,ai[N],bi[N];
int mul(int a,int b,int mod){
    int res=0;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod,b>>=1;
    }
    return res;
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0) return x=1,y=0,a;
    int gcd=exgcd(b,a%b,x,y),t=x;
    x=y,y=t-a/b*y;return gcd;
}
int excrt(){
    int x,y,k,M=bi[1],ans=ai[1];
    for(int i=2;i<=n;++i){
        int a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;
        int gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1;
        x=mul(x,c/gcd,bg);
        ans+=x*M,M*=bg,ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
signed main(){
//    freopen("testdata.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i) bi[i]=read(),ai[i]=read();
    printf("%lld\n",excrt());
    return 0;
}

?