中国剩余定理就是同余方程组除数为质数的特殊情况
我直接用同余方程组解了。
记得exgcd后x要更新
还有先更新b1再更新m1，顺序不能错！！（不然会影响到b1的更新）
#include<cstdio>
#include<cctype>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
void exgcd(ll a, ll b, ll& d, ll& x, ll& y)
{if(!b) { d = a; x = 1; y = 0; }else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}void read(ll& x)
{ll f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-1') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}int main()
{ll n, m1, b1, m2, b2;read(n); read(m1); read(b1);_for(i, 2, n){read(m2); read(b2);ll A = m1, B = m2, K = b2 - b1, d, x, y;exgcd(A, B, d, x, y);x = (x * (K / d) % (B / d) + (B / d)) % (B / d);b1 = m1 * x + b1;m1 = m1 / d * m2; }printf("%lld\n", b1);return 0;
}