【OI·其他笔记】数论

质数和约数

质数是指除了 $1$ 和它本身之外没有其他因数的自然数。

质数判定

判定单个自然数是否为质数，可以使用试除法，在这里不多描述。

1
2
3
4
5
6

bool is_prime(int n){
    if(n < 2) return 0; // 如果n小于2，不是质数，返回0
    for(int i = 2; i <= n / i; i++) // 从2开始逐个尝试除数i，直到i大于n的平方根
        if(n % i == 0) return 0; // 如果i能整除n，说明n不是质数，返回0
    return 1; // 如果没有找到能整除n的除数，说明n是质数，返回1
}

此算法复杂度为 $O(\sqrt {n})$。

而接下来介绍判断 $[L,R]$ 质数的快速筛法。

Eratosthenes筛法 （埃氏筛法）

我们知道一个合数一定可以分解为 $p \times s (s \neq 1)$ 的形式，其中 $p$ 是质数，$s$ 是倍数，如 $6 = 2 \times 3,15 = 3 \times 5$。

那么我们就可以枚举 $[L,R]$ 中的 $p$，对于每个 $p$，枚举 $s$，标记掉合数 $p \times s$，剩下的必然是质数，这就是埃氏筛法。

但是我们会发现，如果使用这样的埃氏筛法，有一些数字会被标记多次，如 $6$，会被 $2$ 和 $3$ 标记两次。

所以我们可以做出一个小小的优化：

对于素数 $p$，只枚举倍数 $x \geq p$ 的数，因为如果 $x < p$，则 $x$ 中一定有比 $p$ 小的质因子，$p \times s$ 会在前面筛选过程中被筛出。

还可以发现，在枚举的过程中，每次筛完后剩下的区间内第一个数一定是质数，原因同上。

所以枚举质数时不需要从 $1$ 枚举到 $n$，只要考虑到 $[2,\sqrt {n}]$ 中的质数即可。

此算法时间复杂度为 $O(\frac {n} {2} + \frac {n} {3} + \frac {n} {5} + …) = O(nloglogn)$

1
2
3
4
5
6
7
8

bool p[MAXN]; // 布尔数组，用于标记数字是否为合数
p[0] = p[1] = 1; // 将0和1标记为合数，因为它们不是质数
for(int i = 2; i <= n; i++){
    if(p[i]) continue; // 如果当前数已经被标记为合数，则跳过，因为它不是质数
    for(int j = i; i * j <= n; j++){
        p[i * j] = 1; // 将当前数的倍数（p * s）标记为合数
    }
}

线性筛法

尽管上面的埃氏筛法已经经过优化，减少了重复枚举的次数，可是合数还是会被重复枚举。

而这里的线性筛法，顾名思义，它的时间复杂度是 $O(n)$ 的。

怎么做到的？

线性筛法每个合数只被它的最小质因数（$pri$）标记，所以每个数最多只会被标记一次。

依次考虑 $2 - n$之间的每一个数 $i$。

如果 $i$ 是质数，则将其保存到质数表中。

否则利用 $i$ 和质数表中的 $pri_j$ 筛去 $i \times pri_j$。

注意，筛的过程中要确保 $pri_j$ 是 $i \times pri_j$ 的最小质因子。

1
2
3
4
5
6
7
8
9
10

bool p[MAXN]; // 布尔数组，用于标记数字是否为合数
int cnt = 0; // 计数器cnt
p[0] = p[1] = 1; // 特判，将0和1标记
for(int i = 2; i <= n; i++){
    if(!p[i]) pri[++cnt] = i; // 如果当前数字i是质数，则将其加入质数数组pri，并增加计数器cnt
    for(int j = 1;pri[j] <= n / i; j ++){
        p[i * pri[j]] = 1; // 将当前数字i与质数数组中的质数相乘得到的倍数标记为合数
        if(i % pri[j] == 0) break; // 如果i能被pri[j]整除，则跳出内层循环，避免重复标记
    }
}

练习1：Prime Distance

$\texttt {Prime Distance}$ $\text {- 洛谷}$

简要题面

• 给定两个整数 $L,R$， 求 $[L,R]$ 中相邻的两个差最大的质数和相邻的两个差最小的质数。

• $1 \le L < R \le 2 ^ {31} - 1,R - L \le 10 ^ 6$

  解题思路

  由于数据范围很大，无法生成 $[1,𝑅]$ 中的所有质数。

  使用筛法求出 $[2,\sqrt{R}]$ 中的所有质数。

  对于每个质数 $𝑝$ 把 𝐿, 𝑅 中能被 𝑝 整除的数标记， 即标记 $i \times p (\lceil \frac {L} {p} \rceil \le i \le \lfloor \frac {R} {p} \rfloor)$为合数。

  将筛出的质数进行相邻两两比较，找出答案即可。

  分解质因数/子

  对于以下问题：

  给定一个正整数 $n$，已知它是两个正整数 $p_1,p_2$（$p_1,p_2$ 均为质数）的乘积，试求出较大的 $p_1$。

  $6 < n \le 10 ^ 9$

  $n$ 的范围较小，考虑暴力枚举：

  1 2 3 4 5 6 7 8 9 10 11 12 13

  #include<bits/stdc++.h> using namespace std; int main(){ int n,i,j; cin>>n; for(i = 2;i <= n / i;i ++){ // 从 2 枚举到 sqrt(n) if(n % i == 0){ // 如果 i 能整除 n，说明 i 是 n 的一个质因子 cout<<n / i<<endl; break; // 找到 ans 退出。 } } return 0; }

  此程序的原理，在这里不多赘述，前文已经写过了原因¹。

  此算法复杂度为 $O(\sqrt n)$。

  同样对于以下问题：

  给定一个正整数 $n$，将它分解质因数并输出。

  $1 \le n \le 10000$

  $n$ 的范围非常小⁴，可以使用暴力：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  vector<int> breakdown(int N) { vector<int> result; for (int i = 2; i * i <= N; i++) { if (N % i == 0) { // 如果 i 能够整除 N，说明 i 为 N 的一个质因子。 while (N % i == 0) N /= i; result.push_back(i); } } if (N != 1) { // 说明再经过操作之后 N 留下了一个素数 result.push_back(N); } return result; }

  此算法复杂度为 $O(\sqrt n)$。

  算术基本定理

  若整数 $𝑁 \geq 2$，那么 $𝑁$ 一定可以唯一地表示为若干质数的乘积。形如

  $$N = p_1 ^ {c_1} p_2 ^ {c_2} ... p_k ^ {c _ k} (p_i\text {为质数},c_i \geq 0)$$

  练习2：细胞分裂

  $\text {细胞分裂}$ $\text {- 洛谷}$

  简要题面

  $\texttt {Hanks}$ 博士正在为一个细胞实验做准备工作，他手里有 $N$ 种细胞，每种细胞经过 $1$ 秒钟可以分裂为 $S_i$个同种细胞。

  他希望能选择一种细胞进行培养，使得细胞的个数能够均分为 $M$ 份样本 $(M = m1 ^ {m2})$，开始实验。

  求选择哪种细胞可以使得实验的开始时间最早。

  如果无论选择哪种细胞都不能满足要求，则输出 $-1$。

  解题思路

  $m1 = p_1 ^ {k_1} \times p_2 ^ {k_2} \times p_3 ^ {k_3} \times p_4 ^ {k_4} \times …$

  $m1 ^ {m2} = p_1 ^ {m2 \times k_1} \times p_2 ^ {m2 \times k_2} \times p_3 ^ {m2 \times k_3} \times p_4 ^ {m2 \times k_4} \times …$

  $S_i = p_1 ^ {c_1} \times p_2 ^ {c_2} \times p_3 ^ {c_3} \times p_4 ^ {c_4} \times …$

  我们需要使 ${S_i} ^ t \mod m1 ^ {m2} = 0$ 成立。

  若质数 $p_i$ 对应的系数 $c_i = 0$ 但 $k_i \neq 0$，则 $S_i$ 无法满足要求，否则需要时间为：

  $$ans_i = \max \Big (\Big \lceil \frac {m2 \times k_j} {c_j} \Big \rceil \Big )$$

  若都无法满足则答案为 $-1$，否则答案为 $\min(𝑎𝑛𝑠_i)$ 。

  约数

  约数的基本性质

  若整数 $n$ 除以整数 $d$ 的余数为 $0$，即 $d$ 能整除 $n$。

  则称 $d$ 是 $n$ 的约数，$n$ 是 $d$ 的倍数。记为 $d | n$。

  若正整数 $n$ 被唯一分解为 $𝑛 = 𝑝1 ^ {𝑐_1} 𝑝_2 ^ {𝑐_2} ⋯ 𝑝𝑚 ^ {𝑐𝑚}$，其中 $𝑐𝑖$ 都是正整数，$𝑝_𝑖$ 都是质数。

  且满足 $𝑝1 < 𝑝𝑖 <. . . < 𝑝_𝑚$，则 $n$ 的正约数集合为 ：

  $$p_1^{c_1} p_2^{c_2}...p_k^{c_k} | 0 \le b_i \le c_i$$

  $n$ 的正约数个数为（约数个数定理）：

  $$(C_1 + 1) \times (c_2 + 1) \times ... (c_m + 1) = \prod _{i = 1} ^ m (c_i + 1)$$

  $n$ 的所有正约数的和为（约数和定理）：

  $$(1 + p_1 + {p_1} ^ 2 + ... + {p_1} ^ {c_1}) \times ... \times (1 + p_m + {p_m} ^ 2 + ... + {p_m} ^ {c_m}) = \prod _{i = 1} ^ m \Big (\sum _{j = 0} ^ {c_i} {p_i} ^ j \Big )$$

  求正约数集合

  想求一个自然数的正约数集合，可以使用试除法。

  一个自然数的 $n$ 的正约数最多有 $2 \sqrt n$ 个。

  1 2 3 4 5 6 7 8 9 10

  int compute_SOPA(int n){ int a[MAXN],tmp = 1; // 初始化 for(int i = 1;i <= n / i;i ++){ if(n % i == 0){ // 判断因数 a[tmp ++] = i; // 加入集合 if(n / i != i)a[tmp ++] = n / i; // 根据除法的性质，用一个因数求出另一个因数，减少循环 } } return a; } // 与判断质数相反QWQ

  此算法的时间复杂度为 $O(\sqrt n)$。

  如果想求 $[1,n]$ 中每个数的的正约数集合，则须使用倍数法。

  $[1,n]$ 每个数的的正约数个数之和约为 $nlogn$ 个。

  1

  // 作者太懒没写

  求正约数个数

  前文已经给出了公式²，此处不再赘述。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  unordered_map<int,int> zjs(int n){ // 分解质因子，但是使用哈希表存储质因子 unordered_map<int,int> pri; for(int i = 2;i <= n / i;i ++){ while(n % i == 0) pri[i] ++,n /= i; } if(n > 1)pri[n] ++; return pri; } unordered_map<int,int> pri = zjs(n); long long sum = 1; // 初始化 sum 为 1 for(auto it:pri) // 遍历 pri sum = sum * (it.second + 1); // it.second 即获取 it 指向元素的 vluae

  求正约数和

  同上，前文给出公式³，此处也不再赘述。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  unordered_map<int,int> zjs(int n){ // 分解质因子，但是使用哈希表存储质因子 unordered_map<int,int> pri; for(int i = 2;i <= n / i;i ++){ while(n % i == 0) pri[i] ++,n /= i; } if(n > 1)pri[n] ++; return pri; } unordered_map<int, int> pri = zjs(n); long long sum = 1; for (auto it:pri) { // 遍历 pri int p = it.first,a = it.second; // p 为 it 指向元素的键（key），a 为 it 指向元素的值（value） long long t = 1; while (a --) t = (t * p + 1); sum *= t; }

练习3：反素数

$\texttt {反素数}$ $\text {- 洛谷}$

简要题面

对于任何正整数 $x$，其约数个数记作 $g(x)$。例如：$g(1)=1,g(6)=4$。

如果某个正整数满足： 对于任意的 $0 < i < x$，都有 $g(x) > g(i)$，那么称 $x$ 为反素数。

求不超过 $N$ 的最大的反素数。

$1 \le N \le 2 \times 10^9$。

解题思路

$[1,N]$ 中最大的反素数，就是 $[1,N]$ 中约数个数最多的数中最小的一个。

$[1,N]$ 中任何数的不同质因子都不会超过 $10$ 个，且所有质因子的指数总和不超过 $30$。

$\forall x \in [1, 𝑁]$，$x$ 为反素数的必要条件是：$x$ 分解质因数后可写作

$2 ^ {c1} \times 3 ^ {c_2} \times 5 ^ {c_3} \times 7 ^ {c_4} \times 11 ^ {c_5} \times 13 ^ {c_6} \times 17 ^ {c_7} \times 19 ^ {c_8} \times 23 ^ {c_9} \times 29 ^ {c{10}}$ 并且 $c1 \geq c_2 \geq … \geq c{10} \geq 0$

综上，DFS 即可。

最大公约数和最小公倍数

$a \neq 0,b \neq 0$

能使 $d|a$ 和 $d|b$ 的最大整数称为 $a$ 和 $b$ 的最大公约数，用 $\gcd(a,b)$ 表示。 或者记为 $(a,b)$。

能使 $a|d$ 和 $b|d$ 的最小整数称为 $a$ 和 $b$ 的最小公倍数，用 $\text {lcm}(a,b)$ 表示。 或者记为 $[a,b]$。

最大公约数与最小公倍数的性质

若 $a|m$ 且 $b|m$，则 $\text {lcm}(a,b) | m$

若 $a,b,m$ 皆为正整数，则 $\text {lcm}(ma,mb) = m \times \text {lcm}(a,b)$

$\text {lcm}(a_1,a_2) = a_1a_2 \div \gcd(a_1,a_2)$

$\text {lcm}(a_1,a_2,a_3) = \text {lcm}(\text {lcm}(a_1,a_2),a_3)$

求解最大公约数

这里有两种算法。

1. 更相减损术

   不详细介绍，只给出公式：

   $$∀𝑎, 𝑏 ∈ ℕ, 𝑏 ≠ 0，有 \gcd(𝑎, 𝑏) = \gcd(𝑏, 𝑎 − 𝑏) = \gcd(𝑎, 𝑎 − 𝑏)$$

1. 欧几里得算法（碾转相除法）

   先放公式：

   $$∀𝑎, 𝑏 ∈ ℕ, 𝑏 ≠ 0,\gcd(𝑎, 𝑏) = \gcd(𝑏,a \mod b)$$

   算法很简单，通俗来讲，就是用 $a \div b$，得到余数 $c$ ，再用 $b \div c$，得到余数 $d$，再用 $c \div d$……

   直到余数为于 $0$，此时，除数即为最大公约数。

   例如求 $\gcd(1997,615)$：

   $1997 ÷ 615 = 3 …152$

   $615 ÷ 152 = 4…7$

   $152 ÷ 7 = 21…5$

   $7 ÷ 5 = 1…2$

   $5 ÷ 2 = 2…1$

   $2 ÷ 1 = 2…0$

   $\gcd(1997,615) = 1$

   按照上面的算法，我们简单的可以写出一个递归函数。

   1 2 3 4

   int gcd(int a, int b){ if(b == 0)return a; return gcd(b,a % b); }

   但是递归是很慢的，我们可以优化出一个循环版本的。

   1 2 3 4 5 6 7 8

   int gcd2(int a,int b){ while(b > 0){ int t = a; a = b; b = t % b; } return a; }

   此算法的时间复杂度为 $O(log n)$

   求解最小公倍数

   求 $\text {lcm}(a,b)$，有一个公式：

   $$\text {lcm}(a,b) = \frac {ab} {\gcd(a,b)}$$

   可以写出代码：

   1	a / gcd(a,b) * b;

   这里有个细节，为了防止 a * b 爆 long long，先除后乘，结果不变。

   互质与欧拉函数

   首先，什么是互质？

   $\forall a,b \in ℕ$，若 $\gcd(a,b) = 1$，则称 $a,b$ 互质。

   $[1,N]$ 中与 $N$ 互质的数的个数被称作欧拉函数，记作 $𝜑(𝑁)$。、

   若 $N = p_1 ^ {c_1} p_2 ^ {c_2}…p_m^{c_m}$，则：

   $$𝜑(𝑁) = N \times \frac {p_1 - 1} {p_1} \times \frac {p_2 - 1} {p_2} \times ... \times \frac {p_m - 1} {p_m} = N \prod _{p|N} \Big (1 - \frac {1} {p} \Big)$$

   欧拉函数的特性

2. $\forall n > 1$，$[1,n]$ 中与 $n$ 互质数的和为 $n \times 𝜑(n) \div 2$。

3. 若 $a,b$ 互质，则 $𝜑(a,b) = 𝜑(a) 𝜑(b)$。

   积性函数：如果 $a,b$ 互质时，有 $f(ab)=f(a) \times f(b)$，那么称函数 $f$ 为积性函数。

4. 若 $f$ 是积极性函数，且在算术基本定理中 $n = \prod {i = 1}^m p_i ^ {c_i}$ 则 $f(n) = \prod {i = 1} ^ m f(p_i ^ {c_i})$。

5. 设 $p$ 为质数，若 $p|n$ 且 $p^2|n$ 则 $𝜑(n) = 𝜑(\frac {n} {p}) \times p$。

6. 设 $p$ 为质数，若 $p|n$ 且 $p^2∤n$ 则 $𝜑(n) = 𝜑(\frac {n} {p}) \times (p - 1)$。

7. $\sum_{d|n} 𝜑(d) = n$。

   练习4：仪仗队

   简要题意

   $\texttt {C}$ 君站在一个由学生组成的 $n \times m$ 的方阵的左后方，如

   1 2 3 4 5 6

   · · · · · · · · · · · · · · · * · · · · C君站在 * 处 · 是学生所站位置

   $\texttt {C}$ 君希望知道他能看到的学生数。

   $1 \le N \le 40000$

   解题思路

   除了 $(1,0) (0,1) (1,1)$ 外，$(x,y)$ 处的学生能被看到，需满足：

   $$1 \le x,y \le N,x ≠ y 并且 \gcd(x,y) = 1$$

   因此，答案为 $3 + 2 \times \sum _{i = 2} ^ {N - 1} 𝜑(i)$。

   线性筛求欧拉函数

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   for(int i=2; i<=n; ++i) { // 从2到n遍历 if(!p[i]) { pri[++cnt] = i; // pri数组存储质数 phi[i] = i-1; // 欧拉函数的初始值 } for(int j=1; j<=cnt && i*pri[j]<=n; ++j) { // 遍历质数数组pri，直到i*pri[j]超过n p[i*pri[j]] = true; // i*pri[j]不是质数（标记为true） if(i % pri[j] == 0) { phi[i*pri[j]] = phi[i] * pri[j]; // 若i是pri[j]的倍数，欧拉函数的计算 break; // 跳出循环 } else { phi[i*pri[j]] = phi[i] * (pri[j] - 1); // 欧拉函数的计算 } } }

   同余

   逆元

   对于一个线性同余方程 $ax \equiv 1 (\mod b)$，则 $x$ 称为 $a \mod b$ 的逆元，记作 $a ^ {-1}$。

   扩展欧几里得求单个逆元

   将线性同余方程 $ax \equiv 1 (\mod b)$ 转化为求解方程 $ax + by = 1$，

   然后利用扩展欧几里得求得解。

   1 2 3 4 5 6 7 8 9 10 11

   void Exgcd(ll a,ll b,ll &x,ll &y) { if (!b) x = 1, y = 0; else Exgcd(b, a % b, y, x), y -= a / b * x; } int main() { ll x, y; Exgcd(a, p, x, y); x = (x % p + p) % p; printf("%d\n",x); //x是a在mod p下的逆元 }

   线性求解多个连续逆元

   首先，我们可以确定 $1 ^ {-1} \equiv 1(\mod p)$，

   然后设 $p = k \times i + r(1 < r < i < p)$，$k$ 是 $p \div i$ 的商，$r$ 是余数。

   再将这个式子放到 $(\mod p)$ 意义下就会得到：

   $$k \times + r \equiv 0 (\mod p)$$

   然后乘上 $i^{-1},r^{-1}$ 就可以得到：

   $$k \times r^{-1} + i^{-1} \equiv 0(\mod p)$$

这样，我们就可以用递推的方式求出 $[1,n]$ 区间的所有逆元了。

1
2
3

inv[1] = 1;
for(int i = 2; i <= n;i ++)
inv[i] = (p - p / i) * inv[p % i] % p;

高斯消元

简单容斥原理

概率与数学期望

PS：因为后面的太难，作者还不会😓，到时候慢慢更新吧！

¹. 见埃氏筛法部分 ↩

². 见约数的基本性质部分「约数个数定理」 ↩

³. 见约数的基本性质部分「约数和定理」 ↩

⁴. 因为复杂度是 $O(\sqrt n)$，所以 $n$ 最大为 $(10^8)^2 = 10^{16}$ ↩