$$ \left\{ \begin{matrix}x\equiv a_{1} \pmod{p_1} \\x\equiv a_{2}\pmod{p_2}\\\cdots\\x\equiv a_{n}\pmod{p_i}\end{matrix} \right.$$
对于这个方程，当所有模数两两互质的时候，可以使用中国剩余定理来求解。
然而，倘若并不满足这个条件，普通的中国剩余定理就未必能够奏效了。
我们尝试将中国剩余定理的成立条件进行推广，从而得到一种被称为「扩展中国剩余定理」的算法，以解决模数并不保证互质的情况下的线性同余方程组求解。
对于每个方程的解，它构成了一个解集。而我们需要找到的是这个解集中最小的且满足下一个方程的正整数解。
容易证明，一些线性同余方程组的解集一定是关于所有模数的最小公约数同余的一个数。
于是，我们令\(x_k\)为方程\(1\to k\)的最小正整数解：
$$\begin{equation}\begin{split}P,st:P&=&lcm({p_{i},i\in [1,k]})\\x_{k+1}&=&x_{k}+tP\\x_{k+1}&\equiv&a_{k+1}&\pmod{p_{k+1}}\\x_{k}+tP&\equiv&a_{k+1}&\pmod{p_{k+1}}\\tP&\equiv&a_{k+1}-x_{k}&\pmod{p_{k+1}}\end{split}\end{equation}$$
最后的那个式子可以转化形式然后上扩欧。
这就完成了一种递推求解不保证模数互质的线性同余方程组的方案。
#include<iostream>
#include<cstdio>
long long MOD=1;
inline long long mlt(long long A,long long X,long long P){
long long BS=A,RT=0;
while(X){
if(X&1){
RT+=BS;
RT%=P;
}
BS+=BS;
BS%=P;
X>>=1;
}
return RT;
}
inline long long gcd(long long A,long long B){
return B?gcd(B,A%B):A;
}
inline long long exgcd(long long A,long long B,long long &X,long long &Y,long long D=0){
return B?(D=exgcd(B,A%B,Y,X),Y-=A/B*X,D):(X=1,Y=0,A);
}
long long n,a[100005],b[100005];
void init(){
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&b[i],&a[i]);
}
long long X,Y,T,C,ans=a[1];
MOD=b[1];
for(int i=2;i<=n;++i){
C=(a[i]-ans%b[i]+b[i])%b[i];
X=exgcd(MOD,b[i],T,Y);
if(C%X!=0){
puts("F**KING HARD!");
return;
}
T=mlt(T,C/X,b[i]/X);
ans+=T*MOD;
MOD/=X;
MOD*=b[i];
ans=(ans%MOD+MOD)%MOD;
}
printf("%lld\n",(ans+MOD)%MOD);
}
int main(){
init();
return 0;
}