实在不想打一大堆的证明和公式。。。。
剩余定理(仅适用于除数之间互质):https://www.cnblogs.com/freinds/p/6388992.html
扩展剩余定理:https://www.cnblogs.com/zwfymqz/p/8425731.html
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
long long n,x,y;
long long c[1000100],m[1000100];
long long gcd(long long a,long long b)
{
if(!b) return a;
return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
long long r=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-(a/b)*y;
return r;
}
long long inv(long long a,long long b)
{
exgcd(a,b,x,y);
while(x<0) x+=b;
return x;
}
long long mul(long long a,long long b,long long c)//和快速幂的原理相同,将乘法转换为加法,这样不会爆long long
{
long long res=0;
while(b)
{
if(b%2==1) res=(res+a)%c;
a=(a+a)%c;
b/=2;
}
return res;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&m[i],&c[i]);
for(int i=2;i<=n;i++)
{
long long m1=m[i-1],m2=m[i],c2=c[i],c1=c[i-1],g=gcd(m1,m2);
long long k=(c2-c1)/g,p1=m1/g,p2=m2/g,t=inv(p1,p2);
m[i]=(m1/g)*m2,t=(t%p2+p2)%p2,k=(k%p2+p2)%p2;//能mod的地方都要mod,如果t,k为负数的话,直接+p2 再%p2会炸,先%p2保证k为绝对值最小的负数,+p2后比为正数
c[i]=(mul(mul(t,k,p2),m1,m[i])+c1+m[i])%m[i];
}
printf("%lld\n",c[n]);
return 0;
}
```