首页 学习笔记

# 中国剩余定理 (CRT)

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

{x≡a1(modm1)x≡a2(modm2)...x≡an(modmn)\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=∏i=1nmiMi=MmiMiti≡1(modmi)M = \prod_{i = 1}^nm_i\\ M_i = \frac{M}{m_i}\\ M_it_i\equiv1\pmod{m_i}

tit_i 相当于是 MiM_i 在模 mim_i 意义下的逆元。

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

x=∑i=1naiMitix = \sum_{i = 1}^na_iM_it_i

进而推出任意解：

x0=x+k×Mx_0 = x + k \times M

# 证明

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

ajMjtj≡0(modmi)a_jM_jt_j \equiv 0 \pmod {m_i}

因为 MjM_j 中包含 mim_i。

当 j=ij = i 时，有：

∑j=1najMjtj≡ai(modmi)\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 就解决了这个问题，也就是模数不互质时的解决方法。
# 解法
同样是这个式子：
{x≡a1(modm1)x≡a2(modm2)...x≡an(modmn)\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}
模数不互质时怎么办呢？
我们考虑能否把两个同余方程合并为一个。
我们对两个方程进行讨论：
{x≡a1(modm1)x≡a2(modm2)\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}& \end{cases}
同余也可以表示为：
x=k1m1+a1=k2m2+a2x = k_1m_1 + a_1 = k_2m_2 + a_2
移项：
k1m1−k2m2=a2−a1k_1m_1 - k_2m_2 = a_2 - a_1
诶，这不就是一个 exgcd 的形式吗，所以容易判断是否有解：
  • gcd⁡(m1,m2)∣(a2−a1)\gcd(m_1, m_2) \mid (a_2 - a_1)，有解。
  • 否则无解。
继续来看这个式子，设：
d=gcd⁡(m1,m2)p1=m1dp2=m2dd = \gcd(m_1, m_2)\\ p_1 = \frac{m_1}{d}\\ p_2 = \frac{m_2}{d}
显然 p1p_1 和 p2p_2 是互质的，代入到原式中：
k1p1−k2p2=a2−a1dk_1p_1 - k_2p_2 = \frac{a_2 - a_1}{d}
这个式子中，左边满足了 gcd⁡(p1,p2)=1\gcd(p1, p2) = 1，右边当且仅当 d∣(a2−a1)d \mid (a_2 - a_1) 才有解，利用 exgcd 求出一组特解：
x1p1+x2p2=1x_1p_1 + x_2p_2 = 1
然后可以直接算出 k1,k2k_1,k_2：
{k1=a2−a1dx1k2=−a2−a1dx2\begin{cases} k1 = \frac{a_2 - a_1}{d}x_1&\\ k2 = -\frac{a_2 - a_1}{d}x_2& \end{cases}
于是：
x=k1m1+a1=a2−a1dx1mi+a1x = k_1m_1 + a_1 = \frac{a_2 - a_1}{d}x_1m_i + a_1
至此，我们成功构造关于方程
{x≡a1(modm1)x≡a2(modm2)\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}& \end{cases}
的一个解，但是整个解系如何构造呢？
定理： 我们有一个特解 x0x_0，那么方程
{x≡a1(modm1)x≡a2(modm2)\begin{cases} x\equiv a_1\ \pmod{m_1}&\\ x\equiv a_2\ \pmod{m_2}& \end{cases}
通解为:
x=x0+k×lcm(m1,m2)x = x_0 + k \times lcm(m_1, m_2)
即
x≡x0(modlcm(m1,m2))x \equiv x_0 \pmod {lcm(m_1, m_2)}
这个构造正确性是显然的。
那么接下来还有一个结论： 0,1,2⋅⋅⋅lcm(m1,m2)0, 1, 2 ···lcm(m_1, m_2) 中只有一个解。
关于这个的证明，只需要设存在 x,y(x,y∈[0,lcm(m1,m2)],x≥y)x, y(x,y \in [0, lcm(m_1, m_2)], \ x \geq y) 都是解。
然后推一下式子即可得出，x,yx, y 都是解当且仅当 x=yx = 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