数论初识

本篇的用意在 恶补 认识 OI 中数论的基础部分。

进阶篇见 这里

一些记号：

• \(\land\) 即 且（和交集 \(\cap\) 是不是很像）
• \(\lor\) 即 或（和并集 \(\cup\) 是不是很像）
• \(\Rightarrow\) 即 能够推出
• \(\Leftrightarrow\) 即 等价（或者说可以正着推出也可以反着推出，这两个说法是等价的）

一、约数、倍数与质合数

前置芝士

• 带余除法：\(a \div b = c \cdots\cdots r\) \(\Rightarrow\) \(a \bmod b = r\)
• 约数与倍数：\(a \bmod b = 0\) \(\Leftrightarrow\) \(b\) 是 \(a\) 的约数（或者说因数） \(\Leftrightarrow\) \(a\) 是 \(b\) 的倍数
• 最大公因数：最大的数使得 \(c\) 同时为 \(a\), \(b\) 的约数，记为 \(\gcd(a, b)\) 或 \((a, b)\)
• 最小公倍数：最小的数使得 \(c\) 同时为 \(a\), \(b\) 的倍数，记为 \(\operatorname{lcm}(a, b)\) 或 \([a, b]\)
• 质数：\(p\) 是质数当且仅当 \(p\) 只有 \(1\) 和 \(p\) 两个约数。特别地，\(1\) 不是质数。（在某些地方，\(a\) 与 \(b\) 互质会记为 \(a \perp b\)，本文也会用到这种记法）
• 质因数：一个数的是质数的因数叫做它的质因数。
• 整除：a 是 \(b\) 的约数 \(\Leftrightarrow\) \(a\) 整除 \(b\) \(\Leftrightarrow\) \(a\mid b\)
• 唯一分解定理：质因数分解方案唯一（这个不用证了吧）
• 质数无限
  • 证明：如果只有 \(k\) 个质数，记为 \(\{p_i\}\)，那么考虑 \(\left(\prod p_i\right) + 1\) 这个数，显然它不是任何 \(p_i\) 的约数，所以要么它是个质数，要么它有一个不等于任何 \(p_i\) 的质因数，两种情况都与假设矛盾。所以质数有无数个。
• \(\pi(n)\)：\(n\) 以内质数个数（希腊字母 \(\text{Pi}\)，大写 \(\Pi\)，小写 \(\pi\)）
• \(\pi(n)\) 是 \(O(\frac{n}{\log n})\) 级别的
• 第 \(n\) 个质数是 \(O(n \log n)\) 级别的
• \(\sum_{i=1}^n \frac{1}{i} = O(\log n)\)
• \(\sum_{1 \le p \le n} \frac{1}{p} = O(\log \log n)\)（p 为质数）
• \(a\mid c \land b\mid c \land (a, b) = 1\Rightarrow ab\mid c\)
• \(a\mid bc \land (a, b) = 1 \Rightarrow a\mid c\)
• \(p\mid ab \Rightarrow p\mid a \lor p\mid b\)（p 为质数）
• \(ab = (a, b) \cdot [a, b]\)

附上一个黑科技：

这份代码可以计算 \(a \times b \bmod mod\)，但是 \(a \times b\) 可以爆 long long。

LL mul(LL a, LL b, LL mod) { return ((unsigned long long)a * b - (unsigned long long)((long double)a / mod * b + 0.5) * mod + mod) % mod; }

计算 gcd

欧几里得算法（辗转相除法）

\(\gcd(a, b) = \gcd(a - b, b) = gcd(a - 2b, b) = \cdots = \gcd(a \bmod b, b)\)

另外，对于 \(\gcd_{i=1}^n a_i\) （\(a_i \le w\)）用欧几里得算法，复杂度 \(O(n + \log w)\)（不是 \(O(n \cdot \log w)\)）

其他算法

\[ \gcd(a, b) = \begin{cases} \gcd(\frac a2, \frac b2)&(2\mid a \land 2\mid b)\\ \gcd(\frac a2, b)&((2\mid a \land 2 \not\mid \ b) \lor (2 \not\mid \ a \land 2\mid b))\\ \gcd(a - b, b)&(2 \not\mid \ a \land 2 \not\mid \ b) \end{cases} \]

复杂度 \(O(\log a + \log b)\)。

裴蜀定理

关于 \(x\), \(y\) 的方程 \(ax + by = d (a, b, x, y \in \mathbb Z)\) 有解 \(\Leftrightarrow\) \((a, b)\mid d\)

证明

我不会证 看 OI Wiki 的证明吧。

拓展欧几里得（exgcd）

思路

解 \(ax + by = 1\)，其中 \((a, b) = 1 \land a, b, x, y \in \mathbb Z\)
（可以将 \(ax + by = c\) 转换成 \(ax' + by' = 1\) 的形式）
原式可化为\(ax + by = (a, b) = 1\)
上式有解则表明 \(bx' + (a \bmod b)y' = (b, a \bmod b) = 1\)有解（裴蜀定理）
即 \(bx' + (a - b \lfloor \frac{a}{b} \rfloor)y' = (b, a \bmod b) = 1\) 有解
也即 \(b(x' - \lfloor \frac{b}{a} \rfloor y') + by' = (a, b \bmod a) = 1\)有解
那么 \(x = y'\)，\(y = x' - \lfloor \frac{a}{b}\rfloor y'\) 我们只需要递归下去就行了！
递归时求得 \(bx' + (a \bmod b)y' = 1\) 的解，然后用上述方法推 \(x\), \(y\)
边界条件？
当 \(b = 0\) 时就得到 \(ax'' + 0y'' = 1 \Rightarrow ax'' = 1\)， 可以证明此时 \(a = 1\)（因为 \((a, b) = 1\)），即 \(x'' = 1, y'' = 0\)

代码

代码

// 计算 ax + by = 1 的解，并返回 gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) { x = 1, y = 0; return a; }
    int g = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - a / b * y;
    return g;
}

例题

洛谷 P1082

// https://www.luogu.com.cn/problem/P1082

#include <cstdio>

const int N = 5e6 + 5;

typedef long long LL;

// ax + by = 1
LL exgcd(LL a, LL b, LL &x, LL &y) {
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	LL g = exgcd(b, a % b, x, y);
	LL tmp = x;
	x = y;
	y = tmp - a / b * y;
	return g;
}

int main() {
	LL a, b;
	std::scanf("%lld%lld", &a, &b);
	LL x, y;
	exgcd(a, b, x, y);
	while(x < 0) x += b;
	x %= b;
	std::printf("%lld\n", x);
	return 0;
}

应用

求逆元。（逆元见下方↓）
\(x \equiv a^{-1} \pmod b \Rightarrow ax \equiv 1 \pmod b \Rightarrow ax + by = 1 (y \in \mathbb Z)\)
可以用拓展欧几里得来推，解出的 \(x\) 即为 \(a\) 的逆元。

二、同余问题

前置芝士

• \(a \equiv b \pmod m \Leftrightarrow m\mid (b - a) \Leftrightarrow a \bmod m = b \bmod m\)
• \(a \equiv b \pmod m \land a \equiv b \pmod n \Rightarrow a \equiv b \pmod{[m, n]}\)
• \((k, m) = d \land ka \equiv kb \pmod m \Rightarrow a \equiv b \pmod{\frac md}\)

逆元

如果有一个 \(b\) 满足 \(ab \equiv 1 \pmod m\)，那么我们把 \(b\) 叫做 \(a\) 的逆元。

容易发现逆元跟除法长得很像，所以我们一般把 \(a\) 的逆元记作 \(a^{-1}\)，有时也用分数线来表示：\(\frac ab \bmod m = ab^{-1} \bmod m\)。

如果有 \((b, m) = 1\)，那么 \(b\) 存在 \(\bmod m\) 意义下的逆元（这个可以用上面的拓展欧几里得来构造证明）

欧拉定理

欧拉函数

所有的 \(i\) 满足 \(0 < i \le n\)，\((i, n) = 1\) 构成了一个 \(\bmod n\) 的简化剩余系。

\(n\) 的简化剩余系的个数记为 \(\varphi(n)\) （希腊字母 \(\text{Phi}\)，大写 \(\Phi\)，小写 \(\phi\)，也写作 \(\varphi\)）

也即，\(n\) 以内与 \(n\) 互质的数的个数记为 \(\varphi(n)\)。

\(\varphi\) 是积性函数，即对于互质的两个数 \(a\) 和 \(b\)，满足 \(\varphi(a) \varphi(b) = \varphi(ab)\)

\(\varphi(n)\) 还有一个求解公式：如果 \(n\) 分解质因数后为 \(\prod_{i=1}^k p_i^{a_i}\)，那么 \(\varphi(n) = n \times \prod_{i=1}^k \frac{p_i - 1}{p_i}\)。应用这个公式我们还可以得到，对于质数 \(p\)，\(\varphi(p) = p - 1\)。

欧拉定理

结论

\((a, m) = 1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod m\)

证明

令 \(S = \{x_1, x_2, \cdots, x_{\varphi(m)}\}\) 为 \(m\) 的简化剩余系，
则 \(S' = \{ax_1, ax_2, \cdots, ax_{\varphi(m)}\}\)也是 \(m\) 的简化剩余系
（这个是简化剩余系的性质）
所以 \(\prod_{x \in S'} x \equiv \prod_{x \in S} x \pmod m\) 即 \(a^{\varphi(m)} \equiv 1 \pmod m\)

应用

\(a^{\varphi(m)} \equiv 1 \pmod m \Rightarrow a^{-1} \equiv a^{\varphi(m) - 1} \pmod m\)
如果 \(m\) 为质数，那么 \(a^{-1} \equiv a^{m - 2} \pmod m\)

线性求逆元

思路

令 \(\lfloor \frac{p}{i}\rfloor = k\)，\(p \bmod i = r\)（即 \(ki + r = p (r < i)\)），
则
\[ \begin{aligned} p &\equiv 0 &\pmod p\\ ki + r &\equiv 0 &\pmod p\\ k\cdot i\cdot (i^{-1}\cdot r^{-1}) + r \cdot (i^{-1} \cdot r^{-1}) &\equiv 0 &\pmod p\\ kr^{-1} + i^{-1} &\equiv 0 &\pmod p\\ i^{-1} &\equiv -kr^{-1} &\pmod p\\ i^{-1} &\equiv -\lfloor \frac pi \rfloor \cdot (p \bmod i)^{-1} &\pmod p \end{aligned} \]

即 inv[i] = (-(p / i) * inv[p % i] % p + p) % p，
也即 inv[i] = (p - p / i) * inv[p % i] % p 。

代码

代码

// 筛出 n 以内的逆元
void get_inv() {
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

例题

洛谷 P3811

// https://www.luogu.com.cn/problem/P3811

#include <cstdio>

const int N = 20000528 + 5;

int inv[N];

int main() {
    int n, p;
    scanf("%d%d", &n, &p);
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    for(int i = 1; i <= n; i++) printf("%d\n", inv[i]);
    return 0;
}

中国剩余定理（CRT）

引入

中国剩余定理解决的问题是，对于若干形如 \(x \equiv r_i \pmod p_i\) 的同余方程，求 \(x\) 的最小正整数解。其中 \(p_i\) 两两互质（如果不满足要用下面的拓展中国剩余定理）

先来看一个例子：

求最小的正整数 \(x\)，满足 \(x \equiv 2 \pmod 3\)，\(x \equiv 3 \pmod 5\)，\(x \equiv 2 \pmod 7\)。

解法：令
\(a\) 为除以 \(3\) 余 \(1\) 的最小的 \(5\) 和 \(7\) 的公倍数，（\(a = 70\)）
\(b\) 为除以 \(5\) 余 \(1\) 的最小的 \(3\) 和 \(7\) 的公倍数，（\(b = 21\)）
\(c\) 为除以 \(7\) 余 \(1\) 的最小的 \(3\) 和 \(5\) 的公倍数。（\(c = 15\)）
然后将 \(a\) 乘上 \(2\)（即 \(x \bmod 3\)），\(b\) 乘上 \(3\)，\(c\) 乘上 \(2\)。（\(a = 140\)，\(b = 63\)，\(c = 30\)）
则 \(x = (a + b + c) \bmod 3 \times 5 \times 7 = 23\)

原理

要想让 \([3, 5, 7]\mid a + b + c\)，最简单的方法是：

• \(a\) 除以 \(3\) 余 \(2\)，并且是 \(5\) 和 \(7\) 的公倍数
• \(b\) 除以 \(5\) 余 \(3\)，并且是 \(3\) 和 \(7\) 的公倍数
• \(c\) 除以 \(7\) 余 \(2\)，并且是 \(3\) 和 \(5\) 的公倍数

那么如何求这样的 \(a\), \(b\), \(c\) 呢？
以 \(a\) 为例，我们先求出除以 \(3\) 余 \(1\) 而且是 \(5\) 和 \(7\) 的公倍数的数，然后再乘 \(2\)。
即把 \([5, 7]\) 乘上 \([5, 7]^{-1} \pmod 3\)（此时除以 \(3\) 余数必为 \(1\)，而且是 \(5\), \(7\) 的倍数），再乘余数 \(2\)。
最后算出 \(a + b + c\)，然后模上 \([3, 5, 7]\) 就是答案。

结论

若有方程： \[ \begin{aligned} x \equiv& r_1 \pmod {p_1}\\ x \equiv& r_2 \pmod {p_2}\\ &\vdots\\ x \equiv& r_n \pmod {p_n} \end{aligned} \]
其中 \(p_1, p_2, \cdots p_n\) 两两互质。
令 \(P = \prod_{i=1}^n p_i\)，\(P_i = \frac{P}{p_i}\)，\(v_i = (P_i)^{-1} \pmod {p_1}\)，
则方程的解为 \(x = \sum_{i=1}^n P_iv_ir_i \bmod P\)

代码

代码

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
int crt() {
    int P = 1;
    for(int i = 1; i <= n; i++) P *= p[i];
    int x = 0;
    for(int i = 1; i <= n; i++) {
        int ret = 1;
        ret = ret * (P / p[i]) % P;
        int inv, tmp;
        exgcd(P / p[i], p[i], inv, tmp);
        while(inv <= 0) inv += p[i];
        inv %= p[i];
        ret = ret * inv % P;
        ret = ret * r[i] % P;
        x = (x + ret) % P;
    }
    return x;
}

例题

洛谷 P1495

// https://www.luogu.com.cn/problem/P1495

#include <cstdio>

const int N = 1e5 + 5;
typedef long long LL;

LL r[N], p[N];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) { x = 1, y = 0; return a; }
    LL g = exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return g;
}
LL crt() {
    LL P = 1;
    for(int i = 1; i <= n; i++) P *= p[i];
    LL x = 0;
    for(int i = 1; i <= n; i++) {
        LL ret = 1;
        ret = ret * (P / p[i]) % P;
        LL inv, tmp;
        exgcd(P / p[i], p[i], inv, tmp);
        while(inv <= 0) inv += p[i];
        inv %= p[i];
        ret = ret * inv % P;
        ret = ret * r[i] % P;
        x = (x + ret) % P;
    }
    return x;
}

int main() {
	std::scanf("%d", &n);
	for(int i = 1; i <= n; i++) std::scanf("%lld%lld", &p[i], &r[i]);
	std::printf("%lld\n", crt());
	return 0;
}

拓展中国剩余定理（exCRT）

拓展中国剩余定理解决的问题和 CRT 差不多，但是不要求 \(p_i\) 两两互质。

与 CRT 不同，这次我们尝试两两合并方程。

考虑两个方程 \(x \equiv a_1 \pmod {b_1}\)，\(x \equiv a_2 \pmod {b_2}\)。

我们将它们转成不定方程：\(x = a_1 + b_1p = a_2 + b_2q\)，即 \(b_1p - b_2q = a_2 - a_1\)。

对于这个方程，我们用拓展欧几里得算出 \(p\) 和 \(q\) 的一组解。（如果 \(a_2 - a_1\) 不能被 \(\gcd(b_1, b_2)\) 整除则无解）

那么这两组方程的解为 \(x \equiv a_1 + b_1p = a_2 + b_2q \pmod {\operatorname{lcm}(b_1, b_2)}\)。

代码

代码

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
LL excrt() {
	LL a1, b1, a2, b2, x, y;
	a1 = r[1], b1 = p[1];
	for(int i = 2; i <= n; i++) {
		a2 = r[i], b2 = p[i];
		if(a2 < a1) std::swap(a1, a2), std::swap(b1, b2);
		LL a = b1, b = b2, c = a2 - a1;
		LL g = exgcd(a, b, x, y);
		if(c % g) return -1;
		a /= g, b /= g, c /= g;
		b1 = lcm(b1, b2);
		y = y * (b1 - c) % b1;
		a1 = (a2 + b2 * y % b1) % b1;
	}
	return a1;
}

例题

洛谷 P4777

注意此题需要用前面的乘法技巧，因为可能会爆 long long。

#include <cstdio>
#include <algorithm>

typedef long long LL;

const int N = 1e5 + 5;

LL r[N], p[N];
int n;

LL gcd(LL x, LL y) { return y == 0 ? x : gcd(y, x % y); }
LL lcm(LL x, LL y) { return x / gcd(x, y) * y; }

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) { x = 1, y = 0; return a; }
	LL x_, y_;
    LL g = exgcd(b, a % b, x_, y_);
    x = y_;
    y = x_ - a / b * y_;
    return g;
}

LL mul(LL a, LL b, LL mod) { return (a * b - (LL)((long double)a / mod * b + 0.5) * mod + mod) % mod; }

// 有两个数组：r[] 和 p[]，分别表示余数和模数
// 一共有 n 组方程
LL excrt() {
	LL a1, b1, a2, b2, x, y;
	a1 = r[1], b1 = p[1];
	for(int i = 2; i <= n; i++) {
		a2 = r[i], b2 = p[i];
		if(a2 < a1) std::swap(a1, a2), std::swap(b1, b2);
		LL a = b1, b = b2, c = a2 - a1;
		LL g = exgcd(a, b, x, y);
		if(c % g) return -1;
		a /= g, b /= g, c /= g;
		b1 = lcm(b1, b2);
		y = mul(y, b1 - c, b1);
		a1 = (a2 + mul(b2, y, b1)) % b1;
	}
	return a1;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", &p[i], &r[i]);
	printf("%lld\n", excrt());
	return 0;
} /*
3
11 6
25 9
33 17
*/

小结

数论初步到这里就差不多了，看到这里说明你已经入门了。

后面的就等到 数论进阶 来讲吧。

完结撒花~