exCRT / 同余方程组

给定 \(n\) 个同余方程如下，满足 \(p_i\ge 1\) 且 \(0\le q_i<p_i\)

\[ \begin{cases} x\equiv q_1 \pmod{p_1}\\ x\equiv q_2 \pmod{p_2}\\ \cdots\\ x\equiv q_n \pmod{p_n} \end{cases} \]

exCRT 可以在 \(O(n\log V)\) 的时间内求出原方程的通解：

\[ x\equiv q\pmod p \]

或者报告无解。

考虑其中两个方程，我们将它们合并成一个，然后重复 \(n-1\) 次即可。两个方程

\[ x\equiv q_1\pmod{p_1}\\ x\equiv q_2\pmod{p_2} \]

等价于 \(\exist k_1,k_2\) 使得

\[ \begin{align*} p_1k_1+q_1=p_2k_2+q_2\\ p_1k_1+p_2(-k_2)=q_2-q_1 \end{align*} \]

然后跑 exgcd，得到一个 \(k_1'\) 满足 \(p_1k_1'\equiv d=\gcd(p_1,p_2)\pmod{p_2}\)，那么若 \(d\nmid(q_2-q_1)\) 则直接报告无解，否则：

\[ p=p_1\frac{p_2}{d}\\ q=p_1\left(k_1'\frac{(q_2-q_1)\bmod{p_2}}{d}\bmod{ \frac{p_2}{d}}\right)+q_1 \]

这样写的话可以适配高精度，只需要执行 \(p\times p\) 级别的运算，和高精度数乘、取模等简单的运算。

P4777 【模板】扩展中国剩余定理（EXCRT）

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n; ll p1, q1, p2, q2;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) return x = 1, y = 0, a;
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    cin >> p1 >> q1;
    for(int i = 2; i <= n; i++) {
        cin >> p2 >> q2;
        ll x, y, d = exgcd(p1, p2, x, y);
        if((q2 - q1) % d != 0) { cout << "-1\n"; return 0; }
        ll tmp = (q2 % p2 - q1 % p2 + p2) % p2 / d; p2 /= d;
        tmp = (__int128)tmp * (x % p2 + p2) % p2;
        q1 = (tmp * p1 + q1) % (p1 *= p2);
    }
    cout << q1 << '\n';

    return 0;
}