学习扩展中国剩余定理前需要学习扩欧求逆元。
\(\left\{\begin{matrix}
x\equiv c_{1}(\mod m_{1})
\\
x\equiv c_{2}(\mod m_{2})
\end{matrix}\right.\)
\(x=c_{1}+m_{1}\times k_{1}=c_{2}+m_{2}\times k_{2}\)
\(m_{1}\times k_{1}=c_{2}-c_{1}+m_{2}\times k_{2}\)
$\frac{m_{1}\times k_{1}}{gcd(m_{1},m_{2})}=\frac{c_{2}-c_{1}}{gcd(m_{1},m_{2})}+\frac{m_{2}\times k_{2}}{gcd(m_{1},m_{2})} $
\(\frac{m_{1}\times k_{1}}{gcd(m_{1},m_{2})}\equiv \frac{c_{2}-c_{1}}{gcd(m_{1},m_{2})}(\mod \frac{m_{2}}{gcd(m_{1},m_{2})} )\)
\(k_{1}\equiv inv(\frac{m_{1}}{\gcd(m_{1},m_{2})},\frac{m_{2}}{\gcd(m_{1},m_{2})} )\times \frac{c_{2}-c_{1}}{\gcd(m_{1},m_{2})}(\mod \frac{m_{2}}{\gcd(m_{1},m_{2})} )\)
$k_{1}= inv(\frac{m_{1}}{\gcd(m_{1},m_{2})},\frac{m_{2}}{\gcd(m_{1},m_{2})} )\times \frac{c_{2}-c_{1}}{\gcd(m_{1},m_{2})}+y\times \frac{m_{2}}{\gcd(m_{1},m_{2})} $
$x=c_{1}+inv(\frac{m_{1}}{\gcd(m_{1},m_{2})},\frac{m_{2}}{\gcd(m_{1},m_{2})} )\times \frac{c_{2}-c_{1}}{\gcd(m_{1},m_{2})}\times m_{1}+y\times \frac{m_{2}\times m_{1}}{\gcd(m_{1},m_{2})} $
\(x\equiv c_{1}+inv(\frac{m_{1}}{\gcd(m_{1},m_{2})},\frac{m_{2}}{\gcd(m_{1},m_{2})} )\times \frac{c_{2}-c_{1}}{\gcd(m_{1},m_{2})}\times m_{1}(\mod \frac{m_{2}\times m_{1}}{\gcd(m_{1},m_{2})})\)
\(c^{'}=c_{1}+inv(\frac{m_{1}}{\gcd(m_{1},m_{2})},\frac{m_{2}}{\gcd(m_{1},m_{2})} )\times \frac{c_{2}-c_{1}}{\gcd(m_{1},m_{2})}\times m_{1}\)
\(m^{'}=\frac{m_{2}\times m_{1}}{\gcd(m_{1},m_{2})}\)
这样就将两个条件合并为一个条件，最后就能将所有条件合成一个条件。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
__int128 a[100010],b[100010];
__int128 w,z;
__int128 gcd(__int128 x,__int128 y){
if(y==0){
w=1;
z=0;
return x;
}
__int128 ans=gcd(y,x%y);
__int128 k=w;
w=z;
z=k-x/y*z;
return ans;
}
__int128 ksm(__int128 x,__int128 y,__int128 mod){
if(y==0){
return 1;
}
__int128 ans=ksm(x,y/2,mod);
ans=ans*ans%mod;
if(y%2==1){
ans=ans*x%mod;
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
long long x,y;
cin>>x>>y;
a[i]=x;
b[i]=y;
}
for(int i=1;i<n;i++){
__int128 g=gcd(a[i],a[i+1]);
gcd(a[i]/g,a[i+1]/g);
b[i+1]=(w*(b[i+1]-b[i])/g%(a[i+1]/g)+(a[i+1]/g))%(a[i+1]/g)*a[i]+b[i];
a[i+1]=a[i]*a[i+1]/g;
b[i+1]=b[i+1]%a[i+1];
}
long long ans=b[n];
cout<<ans;
return 0;
}