公式挂掉太丑了就看这里

数论3：中国剩余定理CRT

中国剩余定理（互质）

不常用

解线性同余方程组：$x\equiv a_i(\mathrm{,,mod,,}m_i)$

若 $m_i$ 两两互质，则一定存在解，且在 $[0,m_1m_2…m_n-1]$ 有唯一解

求解过程：
$$
令M=\prod_{i=1}^n m_i,M_i=\frac M{m_i},,,
解若干个
\begin{cases}
x_i\mathrm{,,mod,,}m_i=1\
x_i\mathrm{,,mod,,}M_i=0
\end{cases}\
设x_i=M_it_i,则解M_it_i\mathrm{,,mod,,} m_i=1,,,,
然后x=\sum_{i=1}^n a_ix_i
$$
为啥最后 $x$ 的求解公式是这个：因为每一项对其余模数的的贡献都是0

由于很少用，且 EXCRT 可以替代他，所以就不放CRT板子了

中国剩余定理（不互质增量法）EXCRT

方程两两联立，再一个一个加入

增量法：
$$
解\begin{cases}
x\equiv a(\mathrm{mod,,}b)\
x\equiv c(\mathrm{mod,,}d)\
\end{cases}
,,,有bt+a\equiv c(\mathrm{mod,,}d)，\
解出t\equiv t_0(\mathrm{mod,,}\frac d{(d, b)}),
得x\equiv x_0(\mathrm{mod,,}[b,d])
$$
板子：

// 合并两个同余方程
void merge(ll &a, ll &b, ll c, ll d) { // d <= 10^9
    // bt = c - a(mod d)
    if (a == -1 && b == -1) return;
    ll x, y;
    ll g = exgcd(b, d, x, y);
    //bx = g(mod d)
    if ((c - a) % g != 0) {
        a = b = -1;
        return;
    }
    d /= g; // d'
    ll t0 = ((c - a) / g) % d * x % d;
    if (t0 < 0) t0 += d;
    // t = t0 (mod d')
    a = b * t0 + a;
    b = b * d;
}

直接判断是否有解

$m$ 为合数

$x\mathrm{,,mod,,}m=a$ 等价于若干个 $x\mathrm{,,mod,,}p=a$ 方程取并集，其中 $p|m$ ，然后把所有方程按素因子分类，看前面是否冲突之后，只考虑次数最高的那个

即判 $x\mathrm{,,mod,,}p_i^{e_i}\equiv?$

CRT 本质作用：合数 $\rightarrow$ 素数幂

void solve () {
    int n;
    cin >> n;
    map <int, vector <pii>> v;
    for (int i = 1; i <= n; i++) {
        ll a, m;
        cin >> a >> m;
        //筛
        for (int j = 2; j * j <= m; j++) {
            if (m % j)  continue;
            int p = j, pe = 1;
            while (m % j == 0)  m /= j, pe *= j;
            //cout << p << ' ' << pe <<  ' ' << a % pe << endl;
            v[p].push_back ({pe, a % pe});
        }
        if (m > 1)  v[m].push_back ({m, a % m});
    }

    // for (auto i : v) {
    //     cout << i.first << ": ";
    //     for (auto j : i.second) cout << j.first << ' ' << j.second << ", ";
    //     cout << endl;
    // }

    for (auto i : v) {
        auto vi = i.second;
        int val = max_element (vi.begin (), vi.end ())->second;
        for (auto j : vi) {
            if (val % j.first != j.second) {
                puts ("No");
                return ;
            }
        }

    }
    puts ("Yes");
}