給定 \(n\) 組非負(fù)整數(shù) \(a_i, b_i\)，其中 \(b_i\) 兩兩互質(zhì)，求解關(guān)于 \(x\) 的方程組的最小非負(fù)整數(shù)解。
\(\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\) 關(guān)于 \(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}\)。□

那我們就求出了原同余方程組的一個最小非負(fù)整數(shù)解。

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;
}