# 中国剩余定理(CRT)

中国剩余定理是用来解决如下问题的：

$\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}&\\ ...\ &\\ x\equiv a_n\ \pmod{m_n} \end{cases}$

注意：模数必须互质。

# 解法

我们设

$M = \prod_{i = 1}^nm_i\\ M_i = \frac{M}{m_i}\\ M_it_i\equiv1\pmod{m_i}$

$t_i$ 相当于是 $M_i$ 在模 $m_i$ 意义下的逆元。

此时我们可以构造出一组解：

$x = \sum_{i = 1}^na_iM_it_i$

进而推出任意解：

$x_0 = x + k \times M$

# 证明

根据数组的含义，容易得到，对于第 $i$ 个同余方程，当 $j \ne i$ 时，都有：

$a_jM_jt_j \equiv 0 \pmod {m_i}$

因为 $M_j$ 中包含 $m_i$ 。

当 $j = i$ 时，有：

$\sum_{j = 1}^na_jM_jt_j \equiv a_i \pmod {m_i}$

证毕.

逆元需要用到扩展欧几里得算法(exgcd)来求解，这里不再赘述，不会的左转百度一下吧QwQ

# 代码

例题：P1495 【模板】中国剩余定理(CRT)/曹冲养猪

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n, mul = 1, ans;
ll a[15], b[15], m[15];

inline void exgcd(ll a, ll b, ll &x, ll &y){
    if(!b) return x = 1, y = 0, void();
    exgcd(b, a % b, x, y);
    ll z = x;
    x = y, y = z - (a / b) * y;
}

signed main(){
    scanf("%lld", &n);
    for(ll i = 1; i <= n; i++){
        scanf("%lld%lld", &a[i], &b[i]);
        mul *= a[i];
    }
    for(ll i = 1; i <= n; i++){
        m[i] = mul / a[i];
        ll x = 0, y = 0;
        exgcd(m[i], a[i], x, y);
        if(x < 0) x += a[i];
        ans += b[i] * m[i] * x;
    }
    printf("%lld\n", ans % mul);
    return 0;
}

（远古代码，有些丑陋，见谅。）

# 扩展中国剩余定理(exCRT)

注意到多了扩展，那么这个扩展在哪里呢？

普通的 CRT 要求模数必须互质，这就很恶心，exCRT 就解决了这个问题，也就是模数不互质时的解决方法。

# 解法

同样是这个式子：

$\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}&\\ ...\ &\\ x\equiv a_n\ \pmod{m_n} \end{cases}$

模数不互质时怎么办呢？

我们考虑能否把两个同余方程合并为一个。

我们对两个方程进行讨论：

$\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{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$

诶，这不就是一个 exgcd 的形式吗，所以容易判断是否有解：

$\gcd(m_1, m_2) \mid (a_2 - a_1)$ ，有解。
否则无解。

继续来看这个式子，设：

$d = \gcd(m_1, m_2)\\ p_1 = \frac{m_1}{d}\\ p_2 = \frac{m_2}{d}$

显然 $p_1$ 和 $p_2$ 是互质的，代入到原式中：

$k_1p_1 - k_2p_2 = \frac{a_2 - a_1}{d}$

这个式子中，左边满足了 $\gcd(p1, p2) = 1$ ，右边当且仅当 $d \mid (a_2 - a_1)$ 才有解，利用 exgcd 求出一组特解：

$x_1p_1 + x_2p_2 = 1$

然后可以直接算出 $k_1,k_2$ ：

$\begin{cases} k1 = \frac{a_2 - a_1}{d}x_1&\\ k2 = -\frac{a_2 - a_1}{d}x_2& \end{cases}$

于是：

$x = k_1m_1 + a_1 = \frac{a_2 - a_1}{d}x_1m_i + a_1$

至此，我们成功构造关于方程
$\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}& \end{cases}$
的一个解，但是整个解系如何构造呢？

定理： 我们有一个特解 $x_0$ ，那么方程
$\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}& \end{cases}$
通解为:

$x = x_0 + k \times lcm(m_1, m_2)$

即

$x \equiv x_0 \pmod {lcm(m_1, m_2)}$

这个构造正确性是显然的。

那么接下来还有一个结论： $0, 1, 2 ···lcm(m_1, m_2)$ 中只有一个解。

关于这个的证明，只需要设存在 $x, y(x,y \in [0, lcm(m_1, m_2)], \ x \geq y)$ 都是解。

然后推一下式子即可得出， $x, y$ 都是解当且仅当 $x = y$ 。

# 代码

#include <bits/stdc++.h>
#define ll long long
#define Int __int128

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3)+ (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const Int N = 1e5 + 10;
Int a1, b1, a2, b2, flag;
ll a[N], b[N], n;

inline Int exgcd(Int a, Int b, Int &x, Int &y){
    if(!b) return x = 1, y = 0, a;
    Int g = exgcd(b, a % b, x, y);
    Int z = x;
    x = y, y = z - (a / b) * y;
    return g;e
}

inline void merge(){
    Int d = b2 - b1, x, y, g;
    g = exgcd(a1, a2, x, y);
    Int mod = a2 / g;
    if(d % g == 0){
        x = ((x * d / g) % mod + mod) % mod;
        b1 = x * a1 + b1;
        a1 = (a1 * a2) / g;
    }else flag = 1;
}

inline Int excrt(){
    a1 = a[1], b1 = b[1];
    for(Int i = 2; i <= n; i++){
        a2 = a[i], b2 = b[i];
        merge();
        if(flag) return -1;
    }
    return b1;
}

signed main(){
    n = read();
    for(Int i = 1; i <= n; i++) a[i] = read(), b[i] = read();
    write(excrt()), puts("");
    return 0;
}

# End

数学

# 中国剩余定理(CRT)

# 解法

# 证明

# 代码

# 扩展中国剩余定理(exCRT)

# 解法

# 代码

# End

群论

20221207