中国剩余定理学习笔记

给定 \(n\) 组非负整数 \(a_i, b_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. 计算出所有 \(a_i\) 的积 \(s\)。
2. 计算出 \(m_i=s\div a_i\)。
3. 计算出 \(m_i\) 关于 \(a_i\) 的逆元 \(x_i\)。
4. 计算出 \(x_0=\sum\limits_{i=1}\limits^{n}{m_i\times x_i\times b_i}\bmod s\)。

证明：首先知道最后的通解一定是 \(x=x_0+k\times s\)。然后再证明 \(\forall i\in [1,n],x_0\equiv b_i\pmod{a_i}\)。\(\forall j\in [1,n]\And j\ne i\)，因为 \(m_j\equiv 0\pmod{a_i}\)，所以 \(m_j\times x_j\times b_j\equiv 0\pmod{a_i}\)，所以 \(x_0=\sum\limits_{i=1}\limits^{n}{m_i\times x_i\times b_i}\bmod s\equiv m_i\times x_i\times b_i\equiv 1\times b_i\equiv b_i\pmod{a_i}\)。□

那我们就求出了原同余方程组的一个最小非负整数解。

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[20],b[20],s=1,ans=0;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++)cin>>a[i]>>b[i],s*=a[i];
	for(ll i=1,x,y;i<=n;i++){
		exgcd(x,y,s/a[i],a[i]);
		ans=(ans+b[i]*s/a[i]*x%s)%s;
	}
	cout<<(ans%s+s)%s;
	return 0;
}