中国剩余定理 (crt)

定义

给定方程组: $$\begin{cases} x\equiv a_1 (\text{mod }m_1) \\
x\equiv a_2 (\text{mod }m_2) \\
… \\
x\equiv a_k (\text{mod }m_k) \\
\end{cases}$$

其中 $a_i \geq 0, m_i > 0, a_i,m_i \in \mathbb{Z}$, 且 $m_i$ 之间两两互质

求满足条件的最小非负整数解 $x$ ?

结论

令 $M = m_1 \cdot m_2 ~… ~m_k$, $M_i = \frac{M}{m_i}$

令 $M_i^{-1}$ 为 $M_i$ 在 $\color{red} \text{mod }m_i$ 意义下的逆元

则,答案为: $x = \sum\limits_{i=1}^{k}a_iM_iM_i^{-1} ~ (\text{mod }M)$

证明

因为 $\forall i \neq j, M_i \equiv 0 ~(\text{mod } m_j)$

所以 $\forall i \neq j, a_iM_iM_i^{-1} \equiv 0~ (\text{mod } m_j)$

所以 $\forall i, x \equiv \sum\limits_{i=1}^{k}a_iM_iM_i^{-1} \equiv a_iM_iM_i^{-1} ~ (\bmod ~m_i)$

又因为 $\forall i, M_iM_i^{-1} \equiv 1 ~(\text{mod } m_i)$

所以 $\forall i, x \equiv a_iM_iM_i^{-1} \equiv a_i ~ (\text{mod } m_i)$

证明推导过程

证明推导过程

这里直接放参考链接一中的片段:

image

由于 $M = 3\times5\times7 = 105$

所以最后的解就是 $x = (n_1 + n_2 + n_3) ~\bmod ~ 105 = 233 ~ \bmod 105 = 23$

例题

  1. https://www.luogu.com.cn/problem/P3868

快速乘

在题目中,有可能出现 $\bmod$ 接近 $1e18$ 的情况,有可能会爆 long long,所以在计算大数乘法时,要用快速乘(原理类似于快速幂):

ll qmul(ll a, ll b) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % mod;
        b >>= 1;
        a = (a + a) % mod;
    }
    return ans;
}

模版

luogu-P3868-AC代码

题目链接: https://www.luogu.com.cn/problem/P3868

#include <bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define ll long long

ll M = 1;

ll qmul(ll a, ll b) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % M;
        b >>= 1;
        a = (a + a) % M;
    }
    return ans;
}

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll g = exgcd(b, a%b, x, y);
    ll curx = y;
    ll cury = x - (a/b) * y;
    x = curx; y = cury;
    return g;
}

ll a[15], b[15];
int k;

ll crt() {
    ll ans = 0;
    for (int i = 1; i <= k; i++) {
        ll m = M / b[i];
        ll x,y;
        exgcd(m, b[i], x, y);
        if (x < 0) x += b[i];

        ans = (ans + qmul(qmul(a[i], m), x)) % M;
    }
    return ans;
}

int main() {
    fastio;

    cin >> k;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i], M *= b[i];

    for (int i = 1; i <= k; i++) {
        a[i] -= (a[i]/b[i]) * b[i];  //将a[i]变成正数
        a[i] += b[i];
        a[i] %= b[i];
    }
    cout << crt() << endl;
}

参考链接

  1. https://zhuanlan.zhihu.com/p/103394468

拓展中国剩余定理 (excrt)

定义

用于 $m_1,m_2,…,m_k$ 并不互质的情况

给定方程组: $$\begin{cases} x\equiv a_1 (\text{mod }m_1) \\
x\equiv a_2 (\text{mod }m_2) \\
… \\
x\equiv a_k (\text{mod }m_k) \\
\end{cases}$$

其中 $a_i \geq 0, m_i > 0, a_i,m_i \in \mathbb{Z}$,($m_i$ 之间无特殊关联)

求满足条件的最小非负整数解 $x$ ?

Intuition

先看一些简单的例子:

$$\begin{cases} x\equiv 2 ~(\text{mod }4) \\
\\
x\equiv 4 ~(\text{mod }6) \\
\end{cases}\Longrightarrow x \equiv 10 ~(\text{mod } 12)$$

$$\begin{cases} x\equiv 4 ~(\text{mod }6) \\
\\
x\equiv 3 ~(\text{mod }5) \\
\end{cases}\Longrightarrow ~\varnothing$$

可以看出几个特点:

  1. 答案的 $\text{mod}$ 为 $\text{lcm}(m_1, m_2)$
  2. 有可能无解 (若$m_1,m_2$互质则必然有解)

推导

考虑 $x$ 满足:

$$\begin{cases} x\equiv a_1 ~(\text{mod }m_1) \\
\\
x\equiv a_2 ~(\text{mod }m_2) \\
\end{cases}$$

则有 $x = k_1m_1 + a_1 = k_2m_2 + a_2$

即:$k_1m_1 - k_2m_2 = a_2 - a_1$

这个方程有解 $\iff \gcd(m_1,m_2) | (a_2 - a_1)$ (即 $(a_2 - a_1)$ 是 $\gcd(m_1,m_2)$ 的倍数)。

如果无解,就直接退出。

如果有解,就用 $exgcd(m_1, m_2, x’, y’)$ 解出 $k_1$ 的值。

设 $\gcd(m_1, m_2) = g$,则 $k_1 = x’ \cdot\frac{a_2 - a_1}{g}$

然后将 $k_1$ 代入 $x = k_1m_1 + a_1$,得到 $x$ 的值,答案就是 $x \equiv (k_1m_1 + a_1) (\text{mod ~lcm}(m_1,m_2))$

这样,$2$个同余方程就转化为了$1$个,用同样的方法继续进行下去,即可化为一个同余方程。

最终的 $\text{mod}$ 数就是 $M = \text{lcm}(m_1, m_2, m_3 … , m_n)$

模版

luogu-P4777-AC代码

题目链接: https://www.luogu.com.cn/problem/P4777

using namespace std;
#include <bits/stdc++.h>

#define ll long long
const int maxn = 1e5+5;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll g = exgcd(b, a%b, x, y);
    ll x2 = x, y2 = y;
    x = y2, y = x2 - a/b * y2;
    return g;
}

ll mul(ll a, ll b, ll mod) {
    ll res = 0;
    while (b) {
        if (b&1) (res += a) %= mod;
        (a += a) %= mod;
        b >>= 1;
    }
    return res;
}

int n;
ll a[maxn], m[maxn];

int main() {
    fastio;

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> m[i] >> a[i];
    ll cura = a[1], curm = m[1];

    for (int i = 2; i <= n; i++) {
        /* m1 = curm, m2 = m[i], a1 = cura, a2 = a[i] */
        ll x,y;
        ll g = exgcd(curm, m[i], x, y);  // g = gcd(curm, m[i])
        ll c = a[i] - cura;  // c = a2 - a1
        c = ((c % m[i]) + m[i]) % m[i];  // 处理负数,注意是 mod m2 (即 m[i])

        if (c % g) {  // 无解
            cout << -1 << endl;
            return 0;
        }

        ll M = (m[i] * (curm / g));  // M = lcm(m1, m2)
        ll k = mul(x, c / g, M);  // k1 = x' * (a2-a1) / g

        cura = (mul(k, curm, M) + cura) % M;  // x = k1m1 + a1
        curm = M;
    }
    cout << (cura % curm + curm) % curm << endl;
}

注意事项

  1. 我们需要处理可能出现的负数!(比如在快速乘的时候,如果 $b$ 为负数就会炸)

    1. 在 $exgcd(a,b,x’,y’)$ 中,$x'$ 有可能为负数。
    2. $c = a_2 - a_1$,则 $c$ 也有可能为负数。

    那么如何处理负数?我们需要找到这个负数对应的 $\text{mod}$为多少,我们可以在等式 $k_1m_1 - k_2m_2 = a_2 - a_1$ 中找到!

    因为我们要求的是 $k_1$ 的值,实际上 $k_1m_1 = (a_2-a_1) + k_2m_2$,即 $k_1m_1 \equiv (a_2-a_1) \text{ (mod } m_2)$

    所以无论是 $k_1 = x’ \cdot\frac{a_2 - a_1}{g}$ 还是 $(a_2-a_1)$,都取一个 $\text{mod } m_2$ 即可!

    代码段:

     ll c = a[i] - cura;
     c = ((c % m[i]) + m[i]) % m[i];  // 处理负数,注意是 mod m2 (即 m[i])
    
     ll k = mul(x, c / g, M);
     // k = ((k % m[i]) + m[i]) % m[i];  可以处理,但是没有必要,因为快速乘中的 a 可以为负数
    
  2. 注意快速乘过程中的 $\text{mod}$ !因为快速乘求的实际上是 $x$ 的值,所以 $\text{mod } M$,其中 M = lcm(curm, m[i])

  3. 我们用 cura, curm 来维护当前的 同余方程,之后记得更新一下 curm = lcm(curm, m[i])

参考链接

  1. https://www.luogu.com.cn/blog/blue/kuo-zhan-zhong-guo-sheng-yu-ding-li