又忘了

不记不行啊这个...

CRT 中国剩余定理

安利一发，wiki 上证明讲得很好：https://zh.wikipedia.org/zh-hans/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86

给定一个同余方程组：
$$x\equiv a_i \pmod {m_i}$$

$m_i$ 互质，求解 $x$ 。

令： $$M=\prod_{i=1}^n m_i$$$$M_i=Mm_i^{-1}$$$$t_iM_i\equiv 1 \pmod{m_i}$$

则方程组的一个解为：
$$x_0=\sum a_it_iM_i$$

方程组的通解为：
$$x=x_0+kM$$

显然方程组在模 $M$ 意义下有唯一解。

证明很简单：
$$\because t_iM_i\equiv 1 \pmod{m_i}$$$$\forall j, j\neq i, t_iM_i\equiv 0 \pmod{m_j}$$
$$\therefore \forall i, x=a_it_iM_i+\sum_{i\neq j} a_jt_jM_j \equiv a_i\cdot 1 + \sum 0 \equiv a_i \pmod{m_i}$$

注意，互质不代表 $m_i$ 是质数，请不要乱上费马小定理，会 gg orz

EXCRT 扩展中国剩余定理

对于 $m_i$ 不互质情况处理。
看了下网上好像这种做法不是很常规。

假设解得前 $k-1$ 个方程解得的通解为：
$$x=x_0+iM \ (i\in \mathbb{Z})$$
$$M=lcm(m_1, m_2, \cdots, m_{k-1})$$

则加入第 $k$ 个方程我们需要找到一个 $t$ 使得：
$$x_0+tM\equiv a_k \pmod {m_k}$$
$$\Rightarrow Mt+ym_k=a_k-x_0$$

解得一个关于 $t$ 的不定方程，我们即可以得到一个新的特解 ${x_0}'=x_0+tM$ 。

EXCRT 无解情况与中途不定方程无解情况相同。

关于通解

若存在两组方程组的解 $x1, x2$ ，则 $x2-x1\equiv 0 \pmod {m_i}$ 。
令 $M=lcm(m_i)$ ，则因此 $M | x2-x1$，所以任意两解的差都会是 $M$ 的倍数。

关于系数

方程带系数是没问题的，因为逆元乘过去再做 EXCRT 与直接做 EXCRT 是等价的，做不做都不会影响通解。
比如 NOI 的屠龙勇士那题，我就用到了带系数的 EXCRT...

示例代码 - EXCRT

// Code by ajcxsu
// Problem: excrt

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

const int N=1e5+10;

ll qass(ll x, ll y, ll mo) {
    return (__int128)x*y%mo;
}

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

ll a[N], m[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>m[i]>>a[i];
    ll nx, ny, x, M, g, c;
    M=m[1], x=a[1];
    for(int i=2;i<=n;i++) {
        g=exgcd(M, m[i], nx, ny);
        c=((a[i]-x)%m[i]+m[i])%m[i];
        nx=qass(nx, c/g, m[i]/g);
        x=x+nx*M, M*=m[i]/g, ((x%=M)+=M)%=M;
    }
    cout<<x<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/crt-excrt.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆