跳转至

中国剩余定理

\[ \nonumber \begin{cases} x&\equiv a_1\pmod{n_1}\\x&\equiv a_2\pmod{n_2}\\&\vdots\\x&\equiv a_k\pmod{n_k} \end{cases} \]
\[ \begin{gather} \nonumber m_i=\frac{n}{n_i}\\\nonumber c_i=m_i\cdot{m_i}^{-1}\pmod{n}\\\nonumber x=\sum_{i=1}^ka_i\cdot{c_i}\pmod{n} \end{gather} \]
模版
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    Exgcd(b, a % b, y, x);
    y -= a / b * x;
}
i64 CRT(const vector<int> &a, const vector<int> &p) {
    // p_i 两两互质
    // ans % p_i = a_i
    i64 n = 1, ans = 0;
    int len = a.size();
    for (int i = 0 ; i < len ; i++) {
        n *= p[i];
    }
    for (int i = 0 ; i < len ; i++) {
        i64 m = n / p[i];
        i64 x, y;
        Exgcd(m, p[i], x, y);
        ans = (ans + (__int128) a[i] * m % n * x % n + n) % n;
    }
    return ans;
}
例题

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷

拓展中国剩余定理

模版
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
i64 Exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i64 d = Exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
i64 ExCRT(const vector<i64> &a, const vector<i64> &p) {
    // ans % p_i = a_i
    i64 n = p[0];
    __int128 ans = a[0];
    int len = a.size();
    for (int i = 1 ; i < len ; i++) {
        i64 x, y;
        i64 c = (a[i] - ans % p[i] + p[i]) % p[i];
        i64 d = Exgcd(n, p[i], x, y);
        if (c % d != 0) {
            return -1LL;
        }
        i64 g = p[i] / d;
        x = (__int128) x * c / d % g;
        ans += x * n;
        n *= g;
        ans = (ans % n + n) % n; 
    }
    return ans;
}
例题

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