$$ x{~}mod{~}a_{1} = m_{1}\\\\ x{~}mod{~}a_{2} = m_{2}\\\\ x = k_{1}a_{1}+m_{1}\\\\ x = k_{2}a_{2}+m_{2}\\\\ k_{1}a_{1}+m_{1} = k_{2}a_{2}+m_{2}\\\\ k_{1}a_{1}-k_{2}a_{2}=m_{2}-m_{1} \\\\ 上式有解<=>gcd(a_{1},a_{2})|m_{2}-m_{1}\\\\ 同时令(上式依然成立)k_{1}’ = k_{1} +K\frac{a_{2}}{d} -①\\\\ k_{2}’ = k_{2}+K\frac{a_{1}}{d} \\\\ 所有的解:\\\\ x=k_{1}’a_{1}+m_{1} -②\\\\ =(k_{1}+K\frac{a_{2}}{d})a_{1}+m_{1}\\\\ =a_{1}k_{1}+m_{1}+k\frac{a_{1}a_{2}}{d} -③\\\\ =x_{0}+ka\\\\ =m_{1}^{next}+k_{1}^{next}a^{next}\\\\继续用当前公式迭代下一个a_{2}、m_{2}公式\\\\ 则答案满足res =满足 x{~}mod{~}a ≡ x_{0}的x中的最小正整数\\\\ 取最小整数=(x_{0}{~}mod{~}a+a){~}mod{~}a\\\\ $$
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d = exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
int n;
cin >> n;
LL x=0,a1,m1;
cin >> a1 >> m1;
for(int i=0;i<n-1;i++)
{
LL m2,a2;
cin >> a2 >> m2;
LL k1,k2;
LL d = exgcd(a1,-a2,k1,k2);//求出k1 k2
if((m2-m1)%d)//如果d=gcd(a1,a2)不能整除(m2-m1)无解
{
x=-1;
break;
}
k1 *=(m2-m1)/d;//等式① 此时的k1是exgcd后迭代到最深的k1 还要缩放回原等式
k1 = (k1%(a2/d)+a2/d)%(a2/d);//等式① 求k1' 每次都要把等式左右尽量变小
x = k1*a1+m1;//等式②
LL a = abs(a1/d*a2);
m1 = k1*a1+m1;//下一个新的等式来之后, 当前两个等式
a1 = a;
}
if(x!=-1)x = (x%a1+a1)%a1;
cout << x << endl;
return 0;
}