上课根据回忆重新推了一遍，发现不会同余方程了。

题意

给定 $n$ 组非负整数 $a_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} $$

推导

考虑依次合并两个方程，直到剩下一个为止。

$$ \begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ \end{cases} $$

首先将方程转化为：

$$ \begin{cases} x = b_1+a_1k_1 \\ x=b_2+a_2k_2 \\ \end{cases} $$

连立为：

$$ a_1k_1-a_2k_2=b_2-b_1 $$

令 $d=\gcd(k_1,k_2),p_1=\frac{a_1}{d},p_2=\frac{a_2}{d}$。

所以原式为：

$$ p_1k_1-p_2k_2=\frac{b_2-b_1}{d} $$

通过 exgcd，得到：

$$ p_1\lambda_1+p_2\lambda_2=1 $$

所以 $k_1$ 的通解为 $\frac{b_2-b_1}{d}\lambda_1$。

原方程组的特解为：$b_1+a_1k_1=b_1+a_1\lambda_1\frac{b_2-b_1}{d}$。

根据定理。（引用同学的，我懒得写了）

原方程的合并结果为：

$$ x \equiv a_1\lambda_1\frac{b_2-b_1}{d}\ ({\rm mod}\ \text{lcm}(b_1,b_2)\ ) $$

这么一直做下去就行了。

代码

#include<algorithm>
#include<iostream>
#define int __int128
using namespace std;
template <typename __Tp> void read(__Tp &x) {
    int f = x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
void read(char &ch) { for (ch = getchar(); isspace(ch); ch = getchar()); }
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &... y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
void write(const char *s) { for (; *s; ++s) putchar(*s); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ... y) { write(x), write(y...); }
struct equation
{
    int a,m;
}a[100005],s;
int n,p;
void exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
}
equation work(equation x,equation y)
{
    equation ans;
    int gcd=__gcd(x.m,y.m),da=y.a-x.a;
    int X,Y;
    exgcd(x.m,y.m,X,Y);
    ans.m=x.m/gcd*y.m;
    X=(X*(da/gcd))%ans.m;
    ans.a=((X*x.m)%ans.m+x.a+ans.m)%ans.m;
    return ans;
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++)read(a[i].m,a[i].a);
    s=a[1];
    for(int i=2;i<=n;i++)s=work(a[i],s);
    write(s.a%s.m);
}