扩展中国剩余定理学习笔记

给定 \(n\) 组非负整数 \(a_i, b_i\) ，求解关于 \(x\) 的方程组的最小非负整数解。
\(\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases}\)

首先我们看一下只有 1 个方程的情况：
$x\equiv b_1\ ({\rm mod}\ a_1)$
那么 \(x\) 就是 \(b_1\bmod{a_1}\)。

然后是 2 个方程的情况：
\(\begin{cases}x\equiv b_1\ ({\rm mod}\ a_1) \\x\equiv b_2\ ({\rm mod}\ a_2)\end{cases}\)
可以改写成 \(\begin{cases}x=b_1+X\times a_1\\x= b_2+Y\times a_2\end{cases}\)。
然后就知道 \(b_1+X\times a_1=b_2+Y\times a_2\)。所以 \(a_1\times X+a_2\times (-Y)=b_2-b_1\)。
这个可以用 exgcd 求。具体方法不赘述。
然后求出 \(X\) 的一个解 \(X_0\)，然后就知道 \(X\) 的通解 \(X=X_0+k\times\frac{(b_2-b_1)\times a_2}{\gcd(a_1,a_2)}\)。然后令 \(p=\frac{(b_2-b_1)\times a_2}{\gcd(a_1,a_2)}\)，就可以求出 \(X\) 的最小正解 \(X_1=(X_0\bmod p+p)\bmod p\)。此时新的 \(A=\operatorname{lcm}(a_1,a_2)\)，\(B=(X_1\times a_1+b_1)\bmod A\)。

然后是多个方程的情况：
每 2 个合并成 1 个，直到只剩下一个同余方程。时间复杂度 \(O(n\log w)\)，其中 \(w\) 是值域。

inline ll lcm(ll a,ll b){
	return a*b/__gcd(a,b);
}
inline void exgcd(ll &x,ll &y,ll a,ll b){
	if(!b){x=1;y=0;return;}
	exgcd(y,x,b,a%b);y-=a/b*x;
}
ll n,A,B;
int main(){
	n=rd();A=rd();B=rd();
	for(ll i=1,a,b,x,y;i<n;i++){
		a=rd();b=rd();
		ll g=__gcd(a,A),mod=A/g;
		exgcd(x,y,a,A);
		x=((x*(B-b)/g)%mod+mod)%mod;
		A=lcm(a,A);
		B=(a*x+b)%A;
	}
	printf("%lld",(long long)(B%A));
	return 0;
}