洛谷 P4777 【模闆】擴充中國剩餘定理（EXCRT）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=100000+100;

ll m[maxn],a[maxn]; // x≡a[i](mod m[i])
int n;

ll mymul(ll a,ll b,ll mod){
    
    ll sum=0;
    while(b){
        
        if(b&1) sum=(sum+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return sum;
}

ll exgcd(ll a,ll b,ll &x,ll &y){
    
    if(b==0){
        
        x=1,y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return gcd;
}

ll kaven(){
    
    ll x,y;
    ll M=m[1],ans=(a[1]%M+M)%M;
    for(int i=2;i<=n;i++){
        
        ll gcd=exgcd(M,m[i],x,y);
        ll c=((a[i]-ans)%m[i]+m[i])%m[i];
        if(c%gcd) return -1;  //無解 
        
        x=mymul(x,c/gcd,m[i]/gcd);
        ans+=x*M;
        M*=m[i]/gcd;
        ans=(ans%M+M)%M;
    }
    return ans;
}

int main(){
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&a[i]);
    printf("%lld\n",kaven());
}