原理构造法

令ans = c1 + c2 .. + cn

ci = 余数 * （c1乘到cn但不乘ci）* （c1乘到cn但不乘ci 的逆元，模ci意义下）

定理：在模M = c1乘到cn 意义下，解唯一。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){//	求解 ax + by = gcd(a,b)if(!b){x = 1,y = 0;return a;}int g = exgcd(b,a%b,x,y);int temp = x;x = y;y = temp-a/b*y;return g;
}
int niyuan(int a,int p){//求 a 在 mod p 意义下的逆元int xx = 0,yy = 0;int g = exgcd(a,p,xx,yy);return (xx+p)%p;
}
bool liEu(int a,int b,int &x,int &y,int c){//求解ax + by = cint g = exgcd(a,b,x,y);if(c % g != 0)return 0;//无解int k = c/g;x*=k;y*=k;return 1;
}
int p[3000100],x[3000100];
int cc = 1,ans;
signed main(){ios::sync_with_stdio(0);int n;cin>>n;for(int i = 1;i <= n;i++){//cout<<i<<endl;cin>>p[i]>>x[i];//x = b mod pcc*=p[i]; }for(int i = 1;i <= n;i++){ans+= (x[i]%cc)*(niyuan(cc/p[i],p[i])%cc)*((cc/p[i])%cc);ans%=cc;}cout<<ans;return 0;
}

int128版

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n,a[20],b[20],m[20],inv[20];
int M=1,ans[20];
__int128 read()
{__int128 res=0;char scan[1005];scanf("%s",scan);for(int i=0;i<strlen(scan);i++)res*=10,res+=scan[i]-'0';return res;
}
void print(__int128 num){if(num>9)print(num/10);putchar(num%10+'0');
}
void exgcd(int a,int b,int &x,int &y){if(b==0){x=(int)1;y=(int)0;}else{exgcd(b,a%b,y,x);y-=a/b*x;}
}
signed main(){n=read();for(int i=1;i<=n;i++){a[i]=read();b[i]=read();M*=a[i];}for(int i=1;i<=n;i++){m[i]=M/a[i];int y;exgcd(m[i],a[i],inv[i],y);// print(inv[i]);inv[i]=(inv[i]%a[i]+a[i])%a[i];// printf("\n");}int ansss=0;for(int i=1;i<=n;i++){ans[i]=(b[i]*inv[i]%M)*m[i]%M;ansss+=ans[i];ansss%=M;}print(ansss%M);return 0;
}