【理论与解析】浅谈初等数论

· · 算法·理论

::::info[作者提示]{open} 本文章内容较多，达到了惊人的 26790 字符，但如果真的想得到初等数论的知识，请认真阅读。接下来是本文提纲。

位序列

:::align{center} 表：原码、反码、补码 ::: ::cute-table{tuack} 位序列 无符号整数 有符号（原码） 有符号（反码） 有符号（补码）
000 0 +0 +0 0
001 1 +1 +1 1
010 2 +2 +2 2
011 3 +3 +3 3
100 4 -0 -3 -4
101 5 -1 -2 -3
110 6 -2 -1 -2
111 7 -3 -0 -1

位运算

:::align{center} 表: 位运算符号与表示对照表 ::: ::cute-table{tuack} 位运算 缩写 数学符号表示 代码符号表示
按位取反 \texttt{NOT} \overline{x} 或 \neg x ~
按位与 \texttt{AND} x \land y &
按位或 \texttt{OR} x \lor y \mid
按位异或 \texttt{XOR} x \oplus y ^

例题讲解

P1441【NOIP1996 提高组】 砝码称重（强化版）

::::info[题目描述与数据范围]{open}

:::: ::::success[如何做这道题（题解）]{open} 假设 m=8，目前 \text{dp} 到第 i 枚砝码重量为 2，前 i−1 枚砝码可以表示出 0,3,4,7 四种质量，看看会如何更新。

::cute-table{tuack} 质量 8 7 6 5 4 3 2 1 0 解释一下
按位 \texttt{OR} 0 1 0 0 1 1 0 0 1 (0,3,4,7) 四种质量
^ 0 0 1 1 0 0 1 0 0 四种质量，向左位移 2 位
结果 0 1 1 1 1 1 1 0 1 按位或的结果

高精度

适用范围

整除

定义

设 a,b\in \mathbb Z 且 a \not = 0，如果存在整数 q，使得 b=a\cdot q，则称 a 整除 b，或者 b 可被 a 整除，记作 a \mid b，此时称 a 是 b 的因数（或约数），b 是 a 的倍数；如果不存在这样的整数 q，则称 a 不整除 b，记作 a \nmid b。

基本性质

设 a,b\in \mathbb Z 且 a \not = 0。

取整函数

定义

对于 x\in \mathbb R，定义向下取整函数和向上取整函数分别为：

⌊x⌋=\max\{n\in\mathbb Z\mid n\leq x\};⌈x⌉=\min\{n\in\mathbb Z\mid n\geq x\}

取整函数通常指向下取整函数，此外还有四舍五入函数。

⌊x+0.5⌋,x\geq0 \\ ⌈x-0.5⌉,x<0 \\ \end{cases}

数论中不常用。注意 ⌊-2.5⌉=-3。

基本性质

设 x,y \in \mathbb R，n \in \mathbb Z。

带余除法

定义

设 a,b\in \mathbb Z,a \not= 0，则存在唯一的整数 q（商）和 r（余数），使得

b=a\cdot q+r \quad (0≤r<|a|)

这样的式子称为 b 除以 a 的带余除法算式，q 称为不完全商（简称商），r 称为余数。

基本性质

设 a,b\in \mathbb Z,a \not= 0，q 是 b 除以 a 的商。

:::align{center} 表：编程语言中，负数的带余除法 :::

::cute-table{tuack} 被除数（b） 除数（a） 算式 商（q） 余数（r）
7 3 7\div 3 2 1
7 -3 7\div (-3) -2 1
-7 3 -7\div 3 -2 -1
-7 -3 -7\div (-3) 2 -1
:::align{center} 表：数学界中，负数的带余除法 ::: ::cute-table{tuack} 被除数（b） 除数（a） 算式 商（q） 余数（r）
7 3 7\div 3 2 1
7 -3 7\div (-3) -2 1
-7 3 -7\div 3 -3 2
-7 -3 -7\div (-3) 3 2

互素与素数

最大公约数与最小公倍数

定义（最大公约数）

设 a_1,a_2,\cdots,a_n 是 n 个不全为零的整数，如果正整数 d 满足：

则称 m 为 a_1, a_2, \ldots, a_n 的 最小公倍数，记作

m = \operatorname{lcm}(a_1, a_2, \ldots, a_n) \quad ; \quad m = [a_1, a_2, \ldots, a_n]

基本性质

设 a, b, c, d \in \mathbb{Z}。

若任意两个 a_i,a_j(i \not =j) 都满足 \gcd(a_i,a_j) = 1，则称它们两两互素。

基本性质

设 a,b,c,d \in\mathbb Z。

例题讲解

P3951【NOIP2017 提高组】小凯的疑惑（强化版）

::::info[题目描述与数据范围]{open}

\begin{cases} 1 & \text{P=true} \\ 0 & \text{P=false}\\ \end{cases} \begin{aligned} f(p, q) &= \sum_{i=1}^{p-1} \left\lfloor \frac{iq}{p} \right\rfloor = \sum_{i=1}^{p-1} \sum_{j=1}^{q-1} \left[ j \leq \left\lfloor \frac{iq}{p} \right\rfloor \right] \\ &= \sum_{i=1}^{p-1} \sum_{j=1}^{q-1} [jp \leq iq] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} [iq < jp] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[ i < \frac{jp}{q} \right] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[ i < \left\lfloor \frac{jp}{q} \right\rfloor \right] \end{aligned} \begin{align*} f(p, q) &= \sum_{i=1}^{p-1} \left\lfloor \frac{iq}{p} \right\rfloor \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} [i < \left\lfloor \frac{jp}{q} \right\rfloor] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \left\lfloor \frac{jp}{q} \right\rfloor \\ &= (p-1)(q-1) - f(q, p) \end{align*} P = \{p \in \mathbb{Z}^+ \mid p > 1 \text{ 且 } p \text{ 是素数}\}

特别地，1 既不是素数也不是合数。

基本性质

设 p 是素数，a, b \in \mathbb{Z}

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}

:::align{center} （其中 p_1 < p_2 < \dots < p_k 是素数，\alpha_i \in \mathbb{N}^*，这也称之为 n 的质因数分解。） ::::

伪代码：质因数分解

Function PrimeFactorization(n):
    factors[] ←[]
    for i ←2 to sqrt(n) do
        while n mod i=0 do
            factors.append(i)
            n ←n div i 
    if n>1 then
        factors.append(n)
    return factors

同余方程与中国剩余定理

同余

定义

设 m \in \mathbb{Z}^+，若 a, b \in \mathbb{Z} 满足 m | (a - b)，则称 a 与 b 模 m 同余，记作

a \equiv b \pmod{m}

此时 m 称为 模数（或模），该式称为 同余式。若 m \nmid (a - b)，则称 a 与 b 模 m 不同余，记作

a \not\equiv b \pmod{m}

基本性质

设 a, b, c, d \in \mathbb{Z}, \, m \in \mathbb{Z}^+

裴蜀定理

定理

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

ax + by = \gcd(a, b)

特别地，a 与 b 互素当且仅当存在整数 x, y 满足

ax + by = 1

例如取 a = 28, b = 19，有 \gcd(28, 19) = 1，存在整数 x = -2, y = 3，使得

28 \times (-2) + 19 \times 3 = -56 + 57 = 1

伪代码

扩展欧几里得算法，输入: a,b 为不同时为 0 的整数；输出: g,x,y 满足

ax +by=g=\gcd(a,b) 
Function ExtendedEuclid(a,b):
    if b=0 then
        return abs(a),sign(a),0
    g,x1,y1 ←
        ExtendedEuclid(b,a mod b)
    x ←y1
    y ←x1-(a ÷b) ×y1
    return g,x,y
= x_1 b + y_1 \left( a - \left\lfloor \frac{a}{b} \right\rfloor b \right) = y_1 a + \left( x_1 - \left\lfloor \frac{a}{b} \right\rfloor y_1 \right) b

以上证明仅在 a, b 非负的情况下有效，但其它情况类似再次提醒，代码中的 a \div b 不等于数学公式中的 \left\lfloor \frac{a}{b} \right\rfloor。

二元一次不定方程 \& 同余方程

定义（二元一次不定方程）

$$A \cdot x + B \cdot y = C$$ 关于 $x, y$ 的全体整数解。 #### 定义（同余方程） $A, B, m$ 均为整数，求出方程 $$A \cdot x \equiv B \pmod{m}$$ 关于 $x$ 的全体整数解。 #### 两者等价 $$A \cdot x + B \cdot y = C \iff B \cdot y = C - A \cdot x$$ $$\quad \quad \quad \quad \quad \quad \iff B \mid C - A \cdot x$$ $$\quad \quad \quad \quad \quad \quad \quad \quad \quad \iff A \cdot x \equiv C \pmod{B}$$ #### 举个栗子 **解**：$A\cdot x +B\cdot y =C

解：\frac A d \cdot x+ \frac B d\cdot y= \frac C d

逆元

定义

设 a, m \in \mathbb{Z}，若存在整数 x 使得

ax \equiv 1 \pmod{m}

则称 x 为 a 模 m 的 逆元（或模逆元），记作 a^{-1} \pmod{m} 或 a^{-1}

aa^{-1} \equiv 1 \pmod{m}

此时也称 a 在模 m 下 可逆（或存在逆元）。若这样的 x 不存在，则称 a 在模 m 下不可逆。

基本性质

设 a, b, m \in \mathbb{Z}。

中国剩余定理

定理

设 m_1, m_2, \dots, m_k 是两两互素的正整数，则对于任意整数 a_1, a_2, \dots, a_k，同余方程组

x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \quad \,\vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

在模 M = m_1m_2\dotsm m_k 的意义下有解且有唯一解。即 [0, M-1] 内存在唯一的整数 x 满足上述所有同余式。

解的存在性

设 M_i = \prod_{j \neq i} m_j = \frac{M}{m_i}，显然 \gcd(m_i, M_i) = 1。 故存在整数 t_i 使得 M_i t_i \equiv 1 \pmod{m_i}，即 t_i 是 M_i 模 m_i 的逆元。构造

x_0 = \sum_{i=1}^k a_i M_i t_i

发现它是同余方程组的一个特解，即满足所有的

x_0 \equiv a_i \pmod{m_i}

解的唯一性

假设 x 和 y 都是同余方程组的解，即对所有 i 有

x \equiv y \equiv a_i \pmod{m_i}

即 m_i \mid (x - y) 对所有 i 成立，因此 \operatorname{lcm}(m_1, m_2, \cdots, m_k) \mid (x - y)。考虑 m_1, m_2, \cdots, m_k 两两互素，\operatorname{lcm}(m_1, m_2, \cdots, m_k) = M。综上，同余方程组的通解为

x \equiv x_0 \equiv \sum_{i=1}^k a_i M_i t_i \pmod{M}

\text{Lucas} 定理

定义

设 n, m, p \in \mathbb{Z}^+ 且 p 为素数，则

\binom{n}{m} \equiv \left( \frac{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \right) \binom{n \bmod p}{m \bmod p} \pmod{p}

其中 \binom{n}{m} 表示组合数（或者二项式系数），表示从 n 个不同元素中选取 m 个元素的不同方式的数目，其计算公式为

\binom{n}{m} = \frac{n!}{m!(n-m)!}

特别地，当 n < m 时，规定 \binom{n}{m} = 0

例题讲解

P2421【NOI2002】荒岛野人

::::info[题目描述与数据范围]{open}

线性筛与欧拉定理

线性筛

综上合数 c=p\times m 由且只由 p 标记。

欧拉函数

定义

设 n \in \mathbb{Z}^+，欧拉函数 \varphi(n) 定义为不超过 n 且与 n 互素的正整数的个数，即

\varphi(n) = \#\{1 \leq k \leq n \mid \gcd(k, n) = 1\}

特别地，规定 \varphi(1) = 1。

基本性质

设 k, m, n \in \mathbb{Z}^+

同余类

定义

设 m \in \mathbb{Z}^+，对于任意整数 a，定义集合

\bar{a} = \{ x \in \mathbb{Z} \mid x \equiv a \pmod{m} \}

称为 a 模 m 的 同余类（或剩余类），其中 a 称为该同余类的代表元。所有模 m 同余类的集合记为

\mathbb{Z}_m = \{ \overline{0}, \overline{1}, \ldots, \overline{m-1}\}

基本性质

设 m \in \mathbb{Z}^+, a, b \in \mathbb{Z}。

剩余系

定义

设 m \in \mathbb{Z}^+，若一个大小为 m 的整数集合 \{a_1, a_2, \dots, a_m\} 其元素模 m 两两不同余，则称之为模 m 的一个完全剩余系，通常取 \{0, 1, \dots, m-1\} 作为标准完全剩余系。

若一组整数 b_1, b_2, \dots, b_{\varphi(m)} 满足：

则称 \{b_1, b_2, \dots, b_{\varphi(m)}\} 为模 m 的一个简化剩余系（或既约剩余系）。

基本性质

设 m \in \mathbb{Z}^+, a_i, b_i, c, k \in \mathbb{Z}

欧拉定理

定理（欧拉定理）

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

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

定理（费马小定理）

若 a, p \in \mathbb{Z}^+ 且 p 是素数，则

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

费马小定理是欧拉定理的素数特殊情况。

费马小定理推论

若 a, p \in \mathbb{Z}^+ 且 p 是素数，则

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

因此，可以使用快速幂求模素数下的逆元。

证明

设与 n 互素的所有正整数为 r_1, r_2, \dots, r_{\varphi(n)}，它们构成模 n 的一个简化剩余系 。由于 \gcd(a, n) = 1，当这些数分别乘以 a 后，得到的数

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

在模 n 意义下仍然构成一个简化剩余系（即它们模 n 两两不同余，且每个数仍与 n 互素）
因此，这两个集合在模 n 意义下是相同的，于是有

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

每个 r_i 与 n 互素，所以 \prod_{i=1}^{\varphi(n)} r_i 也与 n 互素，两边同时约去，得到 a^{\varphi(n)} \equiv 1 \pmod{n}

扩展欧拉定理

定理

设 a, m 为正整数，b 为非负整数，则：

\large \textcolor{teal}{💎} \ \textcolor{orange}{\text{Thank You for Your Attention!}} \ \textcolor{teal}{💎} \color{magenta} \mathfrak{Thank\ You} \quad \mathbb{FOR\ LISTENING} \quad \mathcal{HAVE\ A\ NICE\ DAY!} \def\T{\text{T}} \def\h{\text{h}} \def\a{\text{a}} \def\n{\text{n}} \def\k{\text{k}} \def\s{\text{s}} \color{purple} \T\!\h\!\a\!\n\!\k\!\s