数论全家桶（一）

RpInfinity · 2026-09-15 08:26:36 · 算法·理论

本文使用了 DeepSeek 进行查错。

本文为个人对于数论一部分知识点的整理，由于作者能力有限，可能会有错误或者不给出严格证明的情况，敬请谅解，欢迎提出修正，我会尽量修改，文中的代码不保证正确性。

Upd on 2026-09-21：修改了符号错误。

质数

对于 p\in\mathbb{Z}^+(p\geq 2)，若它的正因数只有 1 和 p，就称为质数，否则称为合数。特别地，1 既不是质数也不是合数。

判断质数

由于质数的因子只有 1 和 p，于是很容易想到直接判断 p 还有没有其他的正因子，易写出以下代码：

bool check(int p) {
    for (int i = 2; i < p; ++i)
        if (p % i == 0) return false;
    return true;
}

注意到任意因子 d\leq\sqrt{p} 均有唯一对应的另一个因子 \frac p d，所以其实枚举到根号就可以了：

bool check(int p) {
    if (p < 2) return false;
    for (int i = 2; (long long)i * i <= p; ++i)
        if (p % i == 0) return false;
    return true;
}

注意到这个方法如果要求出区间内所有的质数是非常慢的。

质数筛

质数筛用于解决区间内筛质数的问题。

考虑到对于每一个 x\geq 2，任意 y\in\mathbb{N}(y\geq 2) 均有 xy 不是质数，所以我们可以对于每一个大于一的数把它两倍及以上的倍数都标记为合数，没有标记的即为质数，设值域为 N，时间复杂度为调和级数 O(N\log N)。

如何优化？对于每一个质数 p，任意 y\in\mathbb{N}(y\geq p)，py 肯定会在枚举 p 的时候被标记，所以我们只需要从每个质数的平方开始标记即可，此时时间复杂度为 O(N\log\log N)，这就是埃氏筛。

现在的做法对于每一个合数还是会有多次标记的情况，我们应当使每个合数只被它最小的质因子标记。

可以改成下面这样：

设 n 是合数，它的最小质因子为 p，有 n=pm，因为 p 是 n 的最小质因子，所以 m 的所有质因子都不小于 p。

当我们外层枚举到 i=m 时，内层从小到大枚举质数 P：

当 P<p 时，因为 m 没有小于 p 的质因子，所以 P\nmid m，不会停止；
当 P=p 时，标记 i\cdot P=mp=n 为合数；
然后检查 i\bmod P。如果 i\bmod p=0 就停止枚举更大的质数。因为此时 p\mid i，对于更大的质数 q>p，iq 的最小质因子仍然是 p，应该留给以后用 p 去筛，否则会重复。

如果 i\bmod p\ne 0，那就继续枚举更大的质数，但这不影响 n 已经被唯一标记。

这就是欧拉筛，正确性显然，我们设值域为 N，质数个数为 M：

int prime[M], idx;
bitset<N + 5> isp;

void euler() {
    isp.set(), isp[0] = isp[1] = 0;
    for (int i = 2; i <= N; ++i) {
        if (isp[i]) prime[++idx] = i;
        for (int j = 1; j <= idx && (long long)i * prime[j] <= N; ++j) {
            isp[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

这种方法只能筛 1\sim n 的质数，那如果筛的是一个 l\sim r 的区间呢？

注意到前文说过每个合数 x 它 \sqrt x 下都一定存在因子，所以对于一个 L\sim R 的区间我们可以先欧拉筛筛出 1\sim\sqrt R 范围下的所有质数，然后对于每一个质数将其在 L\sim R 以内大于等于平方的倍数都筛掉即可，不过注意要筛大于等于平方（保证 L\geq 1）：

int prime[N], idx;
bitset<N> isp;

void euler(int n) {
    isp.set();
    isp[0] = isp[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (isp[i]) prime[++idx] = i;
        for (int j = 1; j <= idx && (ll)i * prime[j] <= n; ++j) {
            isp[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    ll L, R; cin >> L >> R;
    euler(sqrtl(R) + 1);
    vector<bool> ok(R - L + 1, true);
    if (L <= 1) ok[0] = false;
    for (int i = 1; i <= idx; ++i) {
        ll p = prime[i];
        ll st = max(p * p, (L + p - 1) / p * p);
        for (ll j = st; j <= R; j += p)
            ok[j - L] = false;
    }
}

时间复杂度为 O(\sqrt R + len\log\log R)，其中 len = R - L + 1 为区间长度。

整除

设 a,b\in\mathbb{Z},b\ne0，若 \exists x\in\mathbb{Z}，使得 bx = a，那么称 a 能被 b 整除或 b 能整除 a，记做 b\mid a，否则记做 b\nmid a。

有趣的性质：

若 a\mid b 且 a\mid c，则对任意整数 m,n，a\mid (mb+nc)；
若 a\mid b，则对于 \forall c\in\mathbb{Z}，均有 a\mid bc；
若 a\mid b 且 c\mid d，则 ac\mid bd；
若 a,b\in\mathbb{Z}(a,b\neq 0) 那么有 a\mid b,b\mid a \Rightarrow a=\pm b；
若 a\mid b 且 b\ne 0，则 |a|\le |b|，因此非零整数的约数只有有限个；
若 a\mid b，则 \gcd(a,b)=|a|；
若 a\mid bc,\quad \gcd(a,b)=1，则 a\mid c；
若 a\mid c,\quad b\mid c,\quad \gcd(a,b)=1，则 ab\mid c；
对于任意两个不相等的整数 a,b 和正整数 n，都有 (a - b)\mid (a^n - b^n)，可以因式分解 (a^n - b^n) 易发现其有 (a-b) 这个因式，对于任意 d\mid n，还有 a^d - b^d\mid a^n - b^n，正确性易得；
同理若 n 为奇数，则有 a + b\mid a^n + b^n，否则若 n 为偶数，则 a + b\mid a^n - b^n。

当然还有很多有趣的性质，这里就不再列举。

同余

设 a, b, m\in\mathbb Z(m>0)，若 m\mid (a - b)，则称 a,b 模 m 同余，记做 a\equiv b\pmod m，否则称 a,b 模 m 不同余，记做

a\not\equiv b\pmod m.

- $a\bmod m = b\bmod m$（取非负余数）； - $\exists k\in\mathbb Z$，使得 $a=b + km$； **性质**： - $a\equiv a\pmod m$； - $a\equiv b\pmod m\Leftrightarrow b\equiv a\pmod m$； - $a\equiv b\pmod m$ 且 $b\equiv c\pmod m$，则 $a\equiv c\pmod m$； - 若 $a\equiv b\pmod m, c\equiv d\pmod m$，则： - $a + c\equiv b + d\pmod m$； - $a - c\equiv b - d\pmod m$； - $ac\equiv bd\pmod m$。 - $a\equiv b\pmod m$，则对于 $\forall k\in\mathbb Z^+$，均有 $a^k\equiv b^k\pmod m$； - 若 $a\equiv b\pmod m$，则对于 $\forall k\in\mathbb Z,\gcd(k,m)=1$，均有 $ak^{-1}\equiv bk^{-1}\pmod m$，其中 $k^{-1}$ 为 $k$ 在模 $m$ 意义下的逆元。 ## 最大公因数设 $a,b$ 为不全为 $0$ 的整数，若整数 $d$ 同时满足 $d\mid a, d\mid b$，则称 $d$ 为 $a$ 和 $b$ 的**公因数**，所有公因数中最大的称为**最大公因数**，记做 $\gcd(a,b)$ 或者简记为 $(a,b)$。形式化地： $$\gcd(a,b) = \max\{d\in\mathbb{Z}^+\mid d\mid a,d\mid b\}.$$ 若 $a=b=0$，则任意非 $0$ 整数都是它们的公因数，故不存在最大公因数，一般约定 $\gcd(0, 0) = 0$。 **性质**： - $\gcd(a,b)=\gcd(b,a)$； - $\gcd(a,0)=|a|$； - $\gcd(a,b) = \gcd(|a|,|b|)$； - 若 $\gcd(a,b) = 1$，则称 $a$ 与 $b$ 互质； - $\forall k\in\mathbb Z$，$\gcd(ka, kb) = |k|\gcd(a,b)$； - 若将 $a,b$ 质因数分解，则 $\gcd$ 中每个质因子的指数为 $a,b$ 分解后该质因子指数的较小值。 ### 求 $\gcd

枚举，直接从 a,b 较小值从大到小枚举，复杂度为 O(\min(a,b))；
枚举较小数的因子，复杂度大概是 O(\sqrt{\min(a,b)})；
辗转相减法（更相减损法）（默认 a,b 为正整数）：

对于正整数 a,b：
- 若 a = b，则 \gcd(a,b) = a，结束；
- 若 a>b，则 a\gets a-b；
- 若 a < b，则 b\gets b-a。
证明：设 d = \gcd(a, b)，则 d\mid a 且 d\mid b，于是 d\mid (a - b)。因此 d 为 a-b 与 b 的公因数，所以 d\leq\gcd(a-b, b)。反过来，设 e = \gcd(a - b, b)，则 e\mid a - b 且 e\mid b，于是 e\mid a，所以 e 为 a 和 b 的公约数，所以 e\leq\gcd(a, b)。

综上 \gcd(a, b) = \gcd(a - b, b)。
```
 int gcd(int a, int b) {
     if (!a) return b;
     if (!b) return a;
     while (a != b) {
         if (a > b) a -= b;
         else b -= a;
     }
     return a;
 }
```
适用于高精度取模不方便时。
辗转相除法：

注意到辗转相减法会多次重复的减去同一个数，造成了时间的浪费，故将减操作改为取模，此时时间复杂度达到 O(\log\min(a,b))。

然后还有个东西叫 Binary GCD（Stein 算法），利用奇偶性优化更相减损法：

若 a,b 均为偶数，则 \gcd(a,b)=2\gcd(a/2,b/2)；
若一奇一偶，把偶数除以 2，\gcd 不变；
若均为奇数，则用更相减损法得到 |a-b| 与较小者，此时结果一定为偶数，可继续除以 2。

最小公倍数

设 a,b 为正整数，若整数 m 同时满足 a\mid m, b\mid m，则称 m 为 a 和 b 的公倍数，所有公倍数中最小的称为最小公倍数，记做 \operatorname{lcm}(a,b) 或者简记为 [a,b]。

形式化地：

\operatorname{lcm}(a,b) = \min\{m\in\mathbb{Z}^+\mid a\mid m, b\mid m\}.

当 a=0 或 b=0 时 \operatorname{lcm}(a,b) 不存在，一般约定为 0。

性质：

\operatorname{lcm}(a,b)=\operatorname{lcm}(b,a)
\operatorname{lcm}(a,b)=\operatorname{lcm}(|a|,|b|)
若 \gcd(a,b)=1，则 \operatorname{lcm}(a,b)=|ab|
对任意正整数 a,b，\gcd(a,b)\cdot \operatorname{lcm}(a,b)=|ab|，由此可得：
\operatorname{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)}
若 a=\prod p_i^{\alpha_i}，b=\prod p_i^{\beta_i}，则
\operatorname{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}
即每个质因子的指数取两者中的较大值。

剩余系

同余类（剩余类）

固定模数 m > 0。对于所有整数 a，所有与 a 模 m 同余的数组成一个集合：

[a]_m = \{a + km\mid k\in\mathbb Z\}.

这个集合称为模 m 的一个同余类，一共有 m 个不同的同余类：

[0]_m, [1]_m, \dots, [m-1]_m.

完全剩余系

从模 m 的每个同余类中各取一个代表元，组成的集合即为 m 的一个完全剩余系，简称完系，只要求集合中每个元素来自不同的同余类即可。

性质：

若 r_1, r_2, \dots, r_m 为模 m 的完全剩余系，则：

它们模 m 两两不同余；
任意整数 a 满足 \gcd(a, m) = 1，ar_1, ar_2, \dots, ar_m 也是完全剩余系；
更一般地，若 \gcd(a, m) = 1，ar_i + b 也构成完全剩余系。

简化剩余系

只从那些与 m 互质的同余类中各取一个代表元，组成的集合即为 m 的一个简化剩余系，简称缩系，易知缩系的元素个数即为 \varphi(m)。

性质：

若 r_1, r_2, \dots, r_{\varphi(m)} 为模 m 的一个缩系，则：

每个 r_i 与 m 互质；
它们模 m 两两不同余；
若 \gcd(a, m) = 1，则 ar_1, ar_2, \dots, ar_{\varphi(m)} 仍然构成一个模 m 的一个缩系。

欧拉函数

欧拉函数 \varphi(n) 表示 1\sim n 内与 n 互质的数的个数，形式化定义如下：

\varphi(n) = |\{k\in\mathbb Z^+\mid 1\leq k\leq n,\gcd(k, n) = 1\}|.

其中 |S| 表示集合 S 的大小。

性质：

若 p 是质数，则 \varphi(p) = p - 1；
若 p 是质数，k\in\mathbb{Z}^+(k\geq 1)，则 \varphi(p^k) = p^k - p^{k - 1} = p^{k - 1}(p - 1)；
欧拉函数为积性函数，即若 \gcd(m, n) = 1，则 \varphi(mn) = \varphi(m)\varphi(n)；
公式：若
n = \prod^{r}_{i = 1}p_i^{\alpha_i},
其中 p_i 为互不相同的质数，则
\varphi(n) = n\prod^r_{i=1}(1 - \frac{1}{p_i}) = \prod_{i=1}^r p_i^{\alpha_i - 1}(p_i - 1).

欧拉定理

若 a,n\in\mathbb Z^+，且 \gcd(a,n) = 1，则

a^{\varphi(n)}\equiv 1\pmod n.

其中 \varphi(n) 为欧拉函数。

证明：取模 n 的一个缩系：

r_1, r_2, \dots, r_{\varphi(n)},

设整数 a 满足 \gcd(a, n) = 1，所以

ar_1, ar_2, \dots, ar_{\varphi(n)}

也构成模 n 的一个缩系。所以它们的乘积在模 n 意义下同余：

\prod_{i = 1}^{\varphi(n)}ar_i\equiv\prod_{i = 1}^{\varphi(n)}r_i\pmod n.

把 a 提出来：

a^{\varphi(n)}\prod_{i = 1}^{\varphi(n)}r_i\equiv\prod_{i = 1}^{\varphi(n)}r_i\pmod n.

由于每个 r_i 都与 n 互质，所以 \prod r_i 也与 n 互质，可以消掉，得到：

a^{\varphi(n)}\equiv 1\pmod n.

求欧拉函数

如果要求一个数 n 的欧拉函数，显然可以直接套用公式

\varphi(n) = n\prod^r_{i=1}(1 - \frac{1}{p_i})

进行计算，时间复杂度为质因数分解的复杂度，为 O(\sqrt n)。

但要求一个 1\sim n 内的欧拉函数这个时候复杂度已经达到了 O(n\sqrt n)，如果 n\geq 2\times 10^6 此时已经不太能接受了，需要优化。

考虑欧拉函数的性质。

若 \gcd(a,b) = 1，则 \varphi(ab) = \varphi(a)\varphi(b)；
其次对于质数 p，有 \varphi(p) = p - 1；
对于质数幂 \varphi(p^k) = p^{k - 1}(p - 1)。

如果只是用积性，我们只能处理互质的两个数相乘；

但合数 i\cdot p 中，p 可能已经整除 i，这时 \gcd(i,p)\ne 1，不能直接用积性。

欧拉筛恰好解决了这个问题。欧拉筛中，每个合数 i\cdot p 只会被它的最小质因子 p 筛一次。并且筛的时候，我们能立刻判断 p 是否整除 i。这两种情况正好对应 \varphi(i\cdot p) 的两种递推方式：

若 p\nmid i，则 \gcd(i,p)=1，由积性得
\varphi(i\cdot p)=\varphi(i)\cdot\varphi(p)=\varphi(i)\cdot(p-1)
若 p\mid i，则 p 是 i 的最小质因子，i\cdot p 与 i 的质因子集合完全相同，只是 p 的指数多了 1。由公式
\varphi(n)=n\prod_{q\mid n}\left(1-\frac1q\right)
可知
\frac{\varphi(i\cdot p)}{i\cdot p}=\frac{\varphi(i)}{i}
所以此时

我们就在欧拉筛的同时递推出了每个数的欧拉函数，时间复杂度 O(n)。

代码：

int phi[N], prime[N], cnt;
bool vis[N];

void get_phi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && (ll)i * prime[j] <= n; ++j) {
            int p = prime[j];
            vis[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p; break;
            } else phi[i * p] = phi[i] * (p - 1);
        }
    }
}

费马小定理

对于一个质数 p，a\in\mathbb Z 且 p\nmid a，则

a^{p - 1}\equiv 1\pmod p.

证明很简单，注意到 \varphi(p) = p - 1，费马小定理其实就是欧拉定理的特例。

裴蜀定理

设 a,b 是不全为 0 的整数，则存在整数 x,y，使得

ax + by = \gcd(a,b).

即 \gcd(a,b) 可以表示成 a,b 的线性组合。

以下给出两种证明：

取集合
S = \{ax + by\mid x,y\in\mathbb Z, ax+by > 0\}.
显然 S 非空，于是由良序原理，S 中有最小正元素，设其为 d = ax_0 + by_0。

先证明 d\mid a 且 d\mid b：

假设 d\nmid a，那么有 a = qd + r(0<r<d)，那么 r = a - qd，而 d = ax_0 + by_0，代入得到：
r = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)
这里 1-qx_0 和 -qy_0 显然均为整数，所以 r\in S，但是有前提易知 r<d，与 d 为 S 中最小元素矛盾，故 d\mid a，同理可证得 d\mid b。

所以 d 为 a,b 的公因数，所以 d\leq \gcd(a,b)。

同时，因为 \gcd(a,b)\mid a 且 \gcd(a,b)\mid b，所以 \gcd(a,b)\mid ax_0 + by_0 = d，所以 \gcd(a,b)\leq d。

综上所述，d = \gcd(a,b)。
原命题可以转化为此命题：\gcd(a,b) 能表示成 a,b 的整系数线性组合。

设当前两个数为 u,v，并且已知
u=sa+tb,\qquad v=pa+qb
其中 s,t,p,q\in\mathbb Z。

辗转相减做的是：
u-v=(s-p)a+(t-q)b
或者
v-u=(p-s)a+(q-t)b
系数仍然是整数。一直是 a,b 的整系数线性组合。

最终的 \gcd 等于两者之一，显然也是 a,b 的整系数组合，故原命题成立。

那么对于

ax + by = c

若 \gcd(a,b)\mid c 显然该方程也是有解的。

扩展欧几里得算法

用于求解方程 ax + by = \gcd(a,b) 的一组整数解。

欧几里得算法即为前文的辗转相除法，其基于：

\gcd(a,b) = \gcd(b, a\bmod b)

递归时，假设我们已经求出了

bx' + (a\bmod b)y' = \gcd(b, a\bmod b) = d.

我们将

a\bmod b = a - \Big\lfloor\frac a b\Big\rfloor b,

代入上式，得到

bx' + (a - \Big\lfloor\frac a b\Big\rfloor b)y' = d,

整理一下得到

ay' + b(x' - \Big\lfloor\frac a b\Big\rfloor y') = d,

对比原式可以发现

x = y',y = x' - \Big\lfloor\frac a b\Big\rfloor y'.

当递归到 b = 0 的边界时，\gcd(a,0) = a，原方程变为 ax + 0y = a，显然取 x = 1, y = 0 即可，代码如下：

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

迭代版：

int exgcd(int a, int b, int &x, int &y) {
    int x1 = 1, y1 = 0, x2 = 0, y2 = 1;
    while (b) {
        int q = a / b;
        int t = a % b;
        a = b; b = t;

        int tx = x1 - q * x2;
        int ty = y1 - q * y2;
        x1 = x2; y1 = y2;
        x2 = tx; y2 = ty;
    }
    x = x1; y = y1;
    return a;
}

有了特解，求通解就很容易了，设特解为 (x_0, y_0)，d = \gcd(a,b)，通解为：

x = x_0 + \frac b d t \\ y = y_0 - \frac a d t \end{cases}

其中 t\in\mathbb Z。

求解线性同余方程

考虑一个线性同余方程

ax\equiv b\pmod m.

其中 m > 0，求 x 的整数解。

由定义，其等价于存在 y 使得

ax + my = b.

显然可以通过扩欧求解。

逆元

设 m > 0,a\in\mathbb Z。若存在整数 x 使得

ax\equiv 1\pmod m,

则称 x 为 a 在模 m 意义下的乘法逆元，记做

x\equiv a^{-1}\pmod m.

此时也说 a 在模 m 意义下可逆。

逆元是唯一的，证明如下：若 $x_1, x_2$ 均为 $a$ 模 $m$ 的逆元，则 $$ax_1\equiv ax_2\equiv 1\pmod m.$$ 所以 $$m\mid a(x_1 - x_2).$$ 又因为 $\gcd(a,m) = 1$，所以 $m\mid(x_1 - x_2)$，即 $x_1\equiv x_2\pmod m$，在模 $m$ 意义下显然是唯一的。 ### 如何求逆元假设 $a$ 在模 $m$ 意义下存在逆元。 1. **扩展欧几里得**：求解过程相当于解一个同余方程 $$ax\equiv 1\pmod m.$$ 可以转化为 $$ax + my = 1.$$ 此时直接使用扩欧求解即可； 2. **费马小定理**：若 $m$ 为质数，有 $$a^{m - 1}\equiv 1\pmod m.$$ 可以转化为 $$a\times a^{m - 2}\equiv 1\pmod m.$$ 对比原方程易知 $x\equiv a^{m-2}\pmod m$，使用快速幂求解即可； 3. **欧拉定理**：因为 $\gcd(a, m) = 1$，所以有 $$a^{\varphi(m)}\equiv 1\pmod m.$$ 同上，易得 $x\equiv a^{\varphi(m) - 1}\pmod m$，预处理 $m$ 的 $\varphi$ 值然后快速幂即可。 4. **递推求逆元**：需要保证 $m$ 为质数。设 $$m = ki + r,k = \Big\lfloor\frac m i\Big\rfloor, r = m\bmod i(0<r<i).$$ 由 $m = ki + r$，模 $m$ 意义下： $$ki + r\equiv 0\pmod m,$$ 移项得： $$ki\equiv -r\pmod m,$$ 两边同时乘上 $i^{-1}r^{-1}$ 得到： $$kr^{-1}\equiv -i^{-1}\pmod m,$$ 所以 $i^{-1}\equiv -kr^{-1}\pmod m$，即 $$i^{-1}\equiv -\lfloor\frac m i\rfloor\cdot(m\bmod i)^{-1}\pmod m.$$ 需要保证 $n < m$。 ```cpp vector<int> inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (long long)(m - m / i) * inv[m % i] % m; ``` ## 威尔逊定理若 $p$ 为质数，则 $$(p - 1)!\equiv -1\pmod p,$$ 反过来，若整数 $n\geq 2$ 满足 $$(n - 1)!\equiv -1\pmod n$$ 则 $n$ 为质数。因此这是质数的一个充要条件。证明如下：设 $p$ 为质数，考虑模 $p$ 的一个缩系 $$\{1, 2, \dots, p - 1\}.$$ 对于其中任意一个元素 $a$，因为 $\gcd(a,p) = 1$，所以 $a$ 在模 $p$ 意义下存在唯一逆元。如果 $a\neq a^{-1}$，那么它们就是缩系中两个不同的元素，可以两两配对，每一对的乘积都是 $1$。对于 $a=a^{-1}$ 等价于 $$a^2\equiv 1\pmod p,$$ 即 $$(a + 1)(a - 1)\equiv 0\pmod p.$$ 由于 $p$ 为质数没有其他因数，所以 $a\equiv 1\pmod p$ 或 $a\equiv -1\pmod p$。那么缩系中所有元素的积 $$(p - 1)!\equiv 1\cdot(p - 1) \equiv - 1\pmod p.$$ 再证逆命题。设 $n\geq 2$ 且 $(n - 1)!\equiv -1\pmod n$。若 $n\geq 4$ 为合数，设 $n = ab$，其中 $1<a\leq b<n$。 - 若 $a < b$，则 $a$ 和 $b$ 都出现在 $(n - 1)!$ 中，所以 $n = ab\mid (n - 1)!$，于是 $(n - 1)!\equiv 0\pmod n$，矛盾。 - 若 $a = b$，即 $n = a^2$，且 $a > 2$，则 $a$ 和 $2a$ 都出现在 $(n - 1)!$ 中，所以 $a^2 = n\mid (n - 1)!$，矛盾。若 $n = 4$，$(4 - 1)! = 6\equiv 2\pmod 4\neq -1$。所以 $n$ 只能是质数。 ## 中国剩余定理（CRT）我们考虑这样一个问题：给定若干个同余方程 $$\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \vdots \\ x\equiv a_k\pmod {m_k} \\ \end{cases}$$ 保证 $m_1, m_2, \dots, m_k$ 两两互质，求 $x$ 的最小非负整数解。我们希望构造一个 $x$，使得它模每个 $m_i$ 都恰好等于对应的 $a_i$。考虑一个更简单的子问题：能不能构造一个数，它在模 $m_1$ 下为 $1$，在模其他所有 $m_j$ 下为 $0$？如果对每个 $i$ 都能构造出这样的数，记为 $e_i$，那么 $$x = a_1e_1 + a_2e_2 + \cdots + a_ke_k$$ 就一定是解，正确性显然。转化为如何构造出 $e_i$。整理一下 $e_i$ 的限制： - $\forall j\neq i,e_i\equiv 0\pmod {m_j};

e_i\equiv 1\pmod {m_i}.

先看第一个 \forall j\neq i,e_i\equiv 0\pmod {m_j}，那很容易就能想到让 e_i 为其他所有 m_j 的倍数。也就是说，取

M_i = \prod_{j\neq i} m_j = \frac{M}{m_i}.

其中 M 表示所有 m_i 的乘积。

那么第一个就满足了，但是直接令 e_i = M_i 并不能满足第二个条件

e_i\equiv 1\pmod {m_i},

我们并不知道 M_i\bmod m_i 的结果。

显然 M_i 和 m_i 是互质的，所以 M_i 在模 m_i 意义下存在逆元。

那么我们只需要将 M_i^{-1} 作为系数乘到 e_i 上就可以了，而且由于 m_i 两两互质，所以不会对第一个条件造成影响。

我们设 t_i \equiv M_i^{-1}\pmod m_i，那么 x 的解就是

x = \sum_{i = 1}^k a_iM_it_i\pmod M.

并且这个解在模 M 意义下唯一。

唯一性的证明：

假设方程组的解在模 M 的意义下不唯一，设其中两个为 x_1, x_2，那么对于每一个 i 均有

x_1\equiv a_i\pmod {m_i}

以及

x_2\equiv a_i\pmod{m_i}.

两式相减可以得到

m_i\mid (x_1 - x_2).

所以 (x_1-x_2) 同时被 m_1, m_2, \dots, m_k 整除。

又因为 m_i 两两互质，所以它们的乘积 M 也整除 (x_1 - x_2)，所以

x_1\equiv x_2\pmod M

假设不成立，所以解在模 M 意义下唯一。

扩展中国剩余定理

我们将原问题进一步推广，考虑模数不两两互质的情况。

此时 CRT 的构造方法不再适用，因为 M_i 在模 m_i 下的逆元不一定存在。但方程组仍然可能有解，所以需要一个更一般的方法。

一次性处理不了这个问题，那就将其分成子问题。每次只合并两个方程，把两个方程等价地转化成一个新的同余方程。反复合并，直到只剩一个方程，就得到了原方程组的解。

考虑两个方程

\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \end{cases}

由第一个方程，x=a_1+m_1t，代入第二个方程得

m_1t\equiv a_2-a_1\pmod {m_2}

令 d=\gcd(m_1,m_2)，该方程有解当且仅当

d\mid (a_2-a_1)

若有解，两边除以 d：

\frac{m_1}{d}t\equiv \frac{a_2-a_1}{d}\pmod {\frac{m_2}{d}}

此时 \gcd\left(\frac{m_1}{d},\frac{m_2}{d}\right)=1，用扩欧求出逆元即可解出

t\equiv t_0\pmod {\frac{m_2}{d}}

代回 x=a_1+m_1t，并注意 m_1\cdot\frac{m_2}{d}=\operatorname{lcm}(m_1,m_2)，得到合并后的方程

x\equiv a_1+m_1t_0\pmod {\operatorname{lcm}(m_1,m_2)}

对于 k 个方程，依次合并即可。最后得到

x\equiv A\pmod M

其中 M=\operatorname{lcm}(m_1,m_2,\dots,m_k)。

ll exCRT(int k, ll a[], ll m[]) {
    ll A = a[1], M = m[1];
    for (int i = 2; i <= k; ++i) {
        ll d, x, y;
        d = exgcd(M, m[i], x, y);
        if ((a[i] - A) % d) return -1;
        ll t = (a[i] - A) / d * x % (m[i] / d);
        A += M * t;
        M = M / d * m[i];
        A = (A % M + M) % M;
    }
    return A;
}

这第一篇先写到这吧，喜欢的点个赞吧。