0x32约数

定义

若整数 $n$ 除以整数 $d$ 的余数为0，即 $d$ 能整除 $n$ ，则称 $d$ 是 $n$ 的约数， $n$ 是 $d$ 的倍数，记为 $d \mid n$ 。

算术基本定理的推论

在算术基本定理中，若正整数 $N$ 被唯一分解为 $N = p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}$ ，其中 $c_{i}$ 都是正整数， $p_i$ 都是质数，且满足 $p_1 < p_2 < \dots < p_m$ ，则 $N$ 的正约数集合可写作：

$N$ 的正约数个数为（ $\Pi$ 表示连乘积符号，与 $\sum$ 类似）：

$N$ 的所有正约数的和为：

求 $N$ 的正约数集合——试除法

若 $d \geq \sqrt{N}$ 是 $N$ 的约数，则 $N / d \leq \sqrt{N}$ 也是 $N$ 的约数。换言之，约数总是成对出现的（除了对于完全平方数， $\sqrt{N}$ 会单独出现）。

因此，只需要扫描 $d = 1 \sim \sqrt{N}$ ，尝试 $d$ 能否整除 $N$ ，若能整除，则 $N / d$ 也是 $N$ 的约数。时间复杂度为 $O(\sqrt{N})$ 。

int factor[1600], m = 0;  
for (int i = 1; i*i <= n; i++) {  
    if (n % i == 0) {  
        factor[++m] = i;  
        if (i != n/i) factor[++m] = n/i;  
    }  
}  
for (int i = 1; i <= m; i++)  
    cout << factor[i] << endl;

试除法的推论

一个整数 $N$ 的约数个数上界为 $2\sqrt{N}$ 。

求 $1\sim N$ 每个数的正约数集合——倍数法

若用“试除法”分别求出 $1 \sim N$ 每个数的正约数集合，时间复杂度过高，为 $O(N \sqrt{N})$ 。可以反过来考虑，对于每个数 $d$ ， $1 \sim N$ 中以 $d$ 为约数的数就是 $d$ 的倍数 $d, 2d, 3d, \dots, \lfloor N / d \rfloor * d$ 。以下程序采用“倍数法”求出 $1 \sim N$ 每个数的正约数集合：

vector<int> factor[500010];  
for (int i = 1; i <= n; i++)  
    for (int j = 1; j <= n/i; j++)  
        factor[i*j].push_back(i);  
for (int i = 1; i <= n; i++) {  
    for (int j = 0; j < factor[i].size(); j++)  
        printf("%d ", factor[i][j]);  
    puts("");  
}

上述算法的时间复杂度为 $O(N + N / 2 + N / 3 + \dots +N / N) = O(N\log N)$

倍数法的推论

$1 \sim N$ 每个数的约数个数的总和大约为 $N \log N$ 。

【例题】反素数 BZOJ1053

对于任何正整数 $x$ ，其约数的个数记作 $\mathrm{g}(x)$ 。例如 $\mathrm{g}(1) = 1$ ， $\mathrm{g}(6) = 4$ 。

如果某个正整数 $x$ 满足：对于任意的 $0 < i < x$ ，都有 $\mathrm{g}(x) > \mathrm{g}(i)$ ，那么称 $x$ 为反质数。例如整数1,2,4,6等都是反质数。

现在给定一个数 $N(1 \leq N \leq 2 * 10^{9})$ ，请求出不超过 $N$ 的最大的反质数。

引理1：

$1 \sim N$ 中最大的反质数，就是 $1 \sim N$ 中约数个数最多的数中最小的一个。

证明：

设 $m$ 是 $1 \sim N$ 中约数个数最多的数中最小的一个。根据 $m$ 的定义， $m$ 显然满足：

1. $\forall x < m$ ， $\mathbf{g}(x) < \mathbf{g}(m)$

2. $\forall x > m, \mathrm{g}(x) \leq \mathrm{g}(m)$

根据反质数的定义，第一条性质说明 $m$ 是反质数，第二条性质说明大于 $m$ 的数都不是反质数，故 $m$ 即为所求。

引理2：

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

证明：

因为最小的11个质数的乘积 $2*3*5*7*11*13*17*19*23*29*31 > 2*10^9$ ，所以 $N \leq 2*10^9$ 不可能有多于10个不同的质因子。

因为即使只包含最小的质数，仍然有 $2^{31} > 2 * 10^9$ ，所以 $N \leq 2 * 10^9$ 的质因子指数总和不可能超过30。

引理3：

$\forall x \in [1, N]$ , $x$ 为反质数的必要条件是: $x$ 分解质因数后可写作 $2^{c_{1}} * 3^{c_{2}} * 5^{c_{3}} * 7^{c_{4}} * 11^{c_{5}} * 13^{c_{6}} * 17^{c_{7}} * 19^{c_{8}} * 23^{c_{9}} * 29^{c_{10}}$ , 并且 $c_{1} \geq c_{2} \geq \cdots \geq c_{10} \geq 0$ 。

通俗地讲， $x$ 的质因子是连续的若干个最小的质数，并且指数单调递减。

证明：

反证法。由引理2，若 $x$ 的质因数分解式中存在一项 $p^k (p > 29)$ ，则必定有一个不超过29的质因子 $p'$ 不能整除 $x$ 。根据算术基本定理的推论， $x / p^k * p'^k$ 的约数个数与 $x$ 的约数个数相等，但前者更小，这与反质数的定义矛盾。故 $x$ 只包含29以内的质因子。

同理，若 $x$ 的质因子不是连续若干个最小的，或者指数不单调递减，我们也可以通过上述交换质因子的方法，得到一个比 $x$ 更小、但约数个数相等的整数。因此假设不成立，原命题成立。

综上所述，我们可以使用深度优先搜索 (DFS)，尝试依次确定前10个质数的指数，并满足指数单调递减、总乘积不超过 $N$ ，同时记录约数的个数。

在这两个限制条件下，搜索量实际上非常小。每当搜索出一个满足条件的整数时，我们就按照引理1的结论更新答案，最终得到约数个数最多的数中最小的一个。

【例题】余数之和 BZOJ1257

给定正整数 $n$ 和 $k$ , 计算 $(k \bmod 1) + (k \bmod 2) + \dots + (k \bmod n)$ 的值。 $1 \leq n, k \leq 10^9$ 。

注意到 $k \mod i = k - \lfloor k / i \rfloor * i$ ，故可转化为计算 $n * k - \sum_{i=1}^{n} \lfloor k / i \rfloor * i$ 。

对于任意整数 $x \in [1, k]$ , 设 $g(x) = \lfloor k / \lfloor k / x \rfloor \rfloor$ . 显然函数 $f(x) = k / x$ 单调递减, 而 $g(x) \geq \lfloor k / (k / x) \rfloor = x$ , 故 $\lfloor k / g(x) \rfloor \leq \lfloor k / x \rfloor$ 。

另外， $\lfloor k / \mathrm{g}(x)\rfloor \geq \lfloor k / (k / \lfloor k / x\rfloor)\rfloor = \lfloor k / k*\lfloor k / x\rfloor \rfloor = \lfloor k / x\rfloor$ 。故 $\lfloor k / \mathrm{g}(x)\rfloor = \lfloor k / x\rfloor$ 。

进一步可得， $\forall i\in [x,\lfloor k / \lfloor k / x\rfloor ]]$ ， $\lfloor k / i\rfloor$ 的值都相等。

$\forall i \in [1, k], \lfloor k / i \rfloor$ 至多只有 $2\sqrt{k}$ 个不同的值。这是因为当 $i \leq \sqrt{k}$ 时， $i$ 只有 $\sqrt{k}$ 种选择，故 $\lfloor k / i \rfloor$ 至多只有 $\sqrt{k}$ 个不同的值。而当 $i > \sqrt{k}$ 时， $[k / i] < \sqrt{k}$ ，故 $\lfloor k / i \rfloor$ 也至多只有 $\sqrt{k}$ 个不同的值。

综上所述，对于 $i = 1\sim k$ ， $\lfloor k / i\rfloor$ 由不超过 $2\sqrt{k}$ 段组成，每一段 $i\in \left[x,\lfloor k / \lfloor k / x\rfloor \right]$ 中 $\lfloor k / i\rfloor$ 的值都等于 $\lfloor k / x\rfloor$ 。在该段中，算式 $\lfloor k / i\rfloor *i = \lfloor k / x\rfloor *i$ 就是一个公差为 $\lfloor k / x\rfloor$ 的等差数列，可以直接用等差数列求和公式计算。

整个算法的时间复杂度为 $O(\sqrt{k})$ 。

long long n, k, ans;  
int main() {  
    cin >> n >> k; ans = n * k;  
    for (int x = 1, gx; x <= n; x = gx + 1) {  
        gx = k/x ? min(k/(k/x), n) : n;  
        ans -= (k/x) * (x + gx) * (gx - x + 1) / 2;  
    }  
    cout << ans << endl;  
    return 0;

最大公约数

定义

若自然数 $d$ 同时是自然数 $a$ 和 $b$ 的约数，则称 $d$ 是 $a$ 和 $b$ 的公约数。在所有 $a$ 和 $b$ 的公约数中最大的一个，称为 $a$ 和 $b$ 的最大公约数，记为 $\gcd(a, b)$ 。

若自然数 $m$ 同时是自然数 $a$ 和 $b$ 的倍数，则称 $m$ 是 $a$ 和 $b$ 的公倍数。在所有 $a$ 和 $b$ 的公倍数中最小的一个，称为 $a$ 和 $b$ 的最小公倍数，记为 $\operatorname{lcm}(a, b)$ 。

同理，我们也可以定义三个数以及更多个数的最大公约数、最小公倍数。

定理

证明：

设 $d = \gcd (a,b), a_0 = a / d, b_0 = b / d$ 。根据最大公约数的定义，有 $\gcd (a_0, b_0) = 1$ 。再根据最小公倍数的定义，有 $\operatorname{lcm}(a_0, b_0) = a_0 * b_0$ 。

于是 $\operatorname{lcm}(a, b) = \operatorname{lcm}(a_0 * d, b_0 * d) = \operatorname{lcm}(a_0, b_0) * d = a_0 * b_0 * d = a * b / d$ 。

证毕。

九章算术·更相减损术

证明：

根据最大公约数的定义，后者显然成立，我们主要证明前者。

对于 $a, b$ 的任意公约数 $d$ ，因为 $d \mid a, d \mid b$ ，所以 $d \mid (a - b)$ 。因此 $d$ 也是 $b, a - b$ 的公约数。反之亦成立。故 $a, b$ 的公约数集合与 $b, a - b$ 的公约数集合相同。于是它们的最大公约数自然也相等。对于 $a, a - b$ 同理。

证毕。

欧几里得算法

证明：

若 $a < b$ ，则 $\gcd (b,a\bmod b) = \gcd (b,a) = \gcd (a,b)$ ，命题成立。

若 $a \geq b$ ，不妨设 $a = q * b + r$ ，其中 $0 \leq r < b$ 。显然 $r = a \mod b$ 。对于 $a, b$ 的任意公约数 $d$ ，因为 $d \mid a, d \mid q * b$ ，故 $d \mid (a - qb)$ ，即 $d \mid r$ ，因此 $d$ 也是 $b, r$ 的公约数。反之亦成立。故 $a, b$ 的公约数集合与 $b, a \mod b$ 的公约数集合相同。于是它们的最大公约数自然也相等。

证毕。

int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}

使用欧几里得算法求最大公约数的复杂度为 $O(\log (a + b))$ 。欧几里得算法是最常用的求最大公约数的方法。不过，因为高精度除法（取模）不容易实现，需要做高精度运算时，可考虑用更相减损术代替欧几里得算法。

【例题】Hankson的趣味题 NOIP2009/CODEVS1172

有 $n$ 个询问，在每个询问中，先给定四个自然数 $a, b, c, d$ ，然后求有多少个 $x$ 满足 $\gcd(a, x) = c$ 并且 $\operatorname{lcm}(b, x) = d$ 。数据范围： $n \leq 2000, 1 \leq a, b, c, d \leq 2 * 10^9$ 。

解法一

从 $\operatorname{lcm}(b, x) = d$ 可知 $x$ 一定是 $d$ 的约数。于是我们可以立即得到一个朴素算法：用试除法求出 $d$ 的所有约数，逐一判断是否满足这两个条件。时间复杂度为 $O(n\sqrt{d}\log d)$ 。在实际测试中可以得到90分。

我们提到过，虽然 $d$ 的约数个数上界大约是 $\sqrt{d}$ ，但是 $1 \sim d$ 中平均每个数的约数个数大约只有 $\log d$ 。换言之，约数个数在通常情况下远远达不到上界。根据实际测算， $10^9$ 之内的自然数中，约数个数最多的自然数仅有 1536 个约数。

为了尽量避免试除法中不能整除时耗费的时间，我们预处理出 $1 \sim \sqrt{2 * 10^9}$ 之间的所有质数，用搜索算法组成 $d$ 的所有约数，再判断题目中的两个条件是否满足，即可得到100分。当然，我们也有更加标准的解法。

解法二

因为 $x$ 是 $d$ 的约数，所以 $x$ 的质因子一定也是 $d$ 的质因子。我们可以对 $d$ 的每个质因子 $p$ ，计算 $x$ 可能包含多少个 $p$ 。

设 $a, b, c, d, x$ 分别包含 $m_{a}, m_{b}, m_{c}, m_{d}, m_{x}$ 个质因子 $p$ ，其中 $m_{x}$ 是未知量。

根据最大公约数的定义，在 $\gcd (a,x) = c$ 中：

1. 若 $m_{a} > m_{c}$ ，则 $m_{x}$ 只能等于 $m_{c}$ 。

2. 若 $m_{a} = m_{c}$ ，则只需满足 $m_{x} \geq m_{c}$ 即可。

3. 若 $m_{a} < m_{c}$ , 则 $m_{x}$ 无解。

同理，根据最小公倍数的定义，在 $\operatorname{lcm}(b,x) = d$ 中：

1. 若 $m_{b} < m_{d}$ ，则 $m_{x}$ 只能等于 $m_{d}$ 。

2. 若 $m_{b} = m_{d}$ ，则只需满足 $m_{x} \leq m_{d}$ 即可。

3. 若 $m_h > m_d$ ，则 $m_x$ 无解。

结合两种情况，有以下结论：

1. 当 $m_{a} = m_{c} = m_{b} = m_{d}$ 时， $m_{x}$ 只能也等于它们，即 $m_{x}$ 只有一种取法。

2. 当 $m_{a} > m_{c}$ 并且 $m_{b} < m_{d}$ 并且 $m_{c} \leq m_{d}$ 时， $m_{x}$ 可取 $m_{c} \sim m_{d}$ 之间的任意值，共有 $m_{d} - m_{c} + 1$ 种取法。
   3.其他情况， $m_{x}$ 无解。

我们把 $m_x$ 的取法数记为 $cnt_p$ ，也就是 $x$ 包含质因子 $p$ 的方案有 $cnt_p$ 种。根据乘法原理，满足题意的 $x$ 数量即为连乘积：

为了更高效地计算，可以预处理出 $1 \sim \sqrt{2 * 10^9}$ 之间的所有质数，对于每个询问，逐一检查每个质数是不是 $d$ 的约数，若是，按照上述方法计算 $cnt_p$ 。若 $d$ 不能被上述任何质数整除，则说明 $d$ 本身是质数，应计算 $cnt_d$ 。在“反素数”一题中我们已经证明过， $d$ 至多包含 10 个质因子，所以计算量很小，时间主要花费在找 $d$ 的质因子上。根据 0x31 节开头提到的质数分布密度，整个算法的时间复杂度大约是 $O(n \sqrt{d} / \log d)$ 。

互质与欧拉函数

定义

$\forall a, b \in \mathbb{N}$ , 若 $\gcd(a, b) = 1$ , 则称 $a, b$ 互质。

对于三个数或更多个数的情况，我们把 $\gcd(a, b, c) = 1$ 的情况称为 $a, b, c$ 互质。把 $\gcd(a, b) = \gcd(a, c) = \gcd(b, c) = 1$ 称为 $a, b, c$ 两两互质。后者显然是一个更强的条件。

欧拉函数

$1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi (N)$ 。

若在算术基本定理中， $N = p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{m}^{c_{m}}$ ，则：

证明：

设 $p$ 是 $N$ 的质因子, $1 \sim N$ 中 $p$ 的倍数有 $p, 2p, 3p, \dots, (N / p) * p$ , 共 $N / p$ 个。同理, 若 $q$ 也是 $N$ 的质因子, 则 $1 \sim N$ 中 $q$ 的倍数有 $N / q$ 个。如果我们把这 $N / p + N / q$ 个数去掉, 那么 $p * q$ 的倍数被排除了两次, 需要加回来一次。因此, $1 \sim N$ 中不与 $N$ 含有共同质因子 $p$ 或 $q$ 的数的个数为:

实际上，上述思想被称为容斥原理，我们将在0x37节详细介绍。类似地，可以在 $N$ 的全部质因子上使用容斥原理，即可得到 $1\sim N$ 中不与 $N$ 含有任何共同质因子的数的个数，也就是与 $N$ 互质的数的个数。

证毕。

根据欧拉函数的计算式，我们只需要分解质因数，即可顺便求出欧拉函数。

int phi(int n) { int ans  $=$  n; for (int i = 2; i <= sqrt(n); i++) if  $(n \% i == 0)$  { ans  $=$  ans / i \* (i-1); while  $(n \% i == 0)$  n /= i; } if  $(n > 1)$  ans  $=$  ans / n \* (n-1); return ans; }

性质 $1\sim 2$

1. $\forall n > 1$ ， $1\sim n$ 中与 $n$ 互质的数的和为 $n*\varphi (n) / 2$

2. 若 $a, b$ 互质，则 $\varphi(ab) = \varphi(a)\varphi(b)$ 。

证明：

因为 $\gcd (n,x) = \gcd (n,n - x)$ ，所以与 $n$ 不互质的数 $x, n - x$ 成对出现，平均值为 $n / 2$ 。因此，与 $n$ 互质的数的平均值也是 $n / 2$ ，进而得到性质1。

根据欧拉函数的计算式，对 $a, b$ 分解质因数，直接可得性质2。把性质2推广到一般的函数上，可以得到“积性函数”的概念。

证毕。

积性函数

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

性质3~6

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

2. 若 $p \mid n$ 且 $p^2 \mid n$ ，则 $\varphi(n) = \varphi(n / p) * p^{10}$ 。

3. 若 $p \mid n$ 但 $p^2 \nmid n$ ，则 $\varphi(n) = \varphi(n / p) * (p - 1)$ 。

4. $\sum_{d|n}\varphi (d) = n$

证明：

把 $n$ 分解质因数，按照积性函数的定义，性质3显然成立。

若 $p|n$ 且 $p^2 |n$ ，则 $n,n / p$ 包含相同的质因子，只是 $\mathcal{P}$ 的指数不同。直接把 $\varphi (n)$ 与 $\varphi (n / p)$ 按照欧拉函数的计算公式写出，二者相除，商为 $\mathcal{P}$ ，所以性质4成立。

若 $p \mid n$ 但 $p^2 \nmid n$ , 则 $n, n / p$ 互质, 由 $\varphi$ 是积性函数得 $\varphi(n) = \varphi(n / p) * \varphi(p)$ , 而 $\varphi(p) = p - 1$ , 所以性质5成立。

设 $f(n) = \sum_{d\mid n}\varphi (d)$ 。用乘法分配律展开比较，再利用 $\varphi$ 是积性函数，得到：若 $n,m$ 互质，则 $f(nm) = \sum_{d\mid nm}\varphi (d) = \left(\sum_{d\mid n}\varphi (d)\right)*\left(\sum_{d\mid m}\varphi (d)\right) = f(n)*f(m)$ 。即 $\sum_{d\mid n}\varphi (d)$ 是积性函数。对于单个质因子， $f(p^{m}) = \sum_{d\mid p^{m}}\varphi (d) = \varphi (1) + \varphi (p) +$ $\varphi (p^2) + \dots +\varphi (p^m)$ 是一个等比数列求和再加1，结果为 $p^m$ 。所以 $f(n) =$ \prod_{i = 1}^{m}f\bigl {(}p_i^{c_i}\bigr) = \prod_{i = 1}^{m}p_i^{c_i} = n ，性质6成立。

证毕。

有关积性函数还有许多内容，并可延伸出狄利克雷卷积、莫比乌斯反演以及一系列相关的快速求和问题。这些内容比较高深，超出了我们的探讨范围，学有余力的读者可

以自行查阅相关资料。

【例题】VisibleLatticePoints FOJ3090

在一个平面直角坐标系的以 $(0,0)$ 为左下角、 $(N,N)$ 为右上角的矩形中，除了 $(0,0)$ 之外，每个坐标上都插着一个钉子，如右图所示。

求在原点向四周看去，能够看到多少个钉子。一个钉子能被看到，当且仅当连接它和原点的线段上没有其他钉子。右图也画出了所有能看到的钉子以及视线。 $1 \leq N \leq 1000$ 。

分析题目容易发现，除了(1,0)、(0,1)和(1,1)这三个钉子外，一个钉子 $(x,y)$ 能被看到，当且仅当 $1\leq x,y\leq N$ ， $x\neq y$ 并且 $\gcd (x,y) = 1$ 。

在 $1 \leq x, y \leq N, x \neq y$ 中能看到的钉子关于过 $(0,0)$ 和 $(N,N)$ 的直线对称。我们可以考虑其中的一半，即 $1 \leq x < y \leq N$ 。换言之，对于每个 $2 \leq y \leq N$ ，我们需要统计有多少个 $x$ 满足 $1 \leq x < y$ 并且 $\gcd(x,y) = 1$ 。这样的 $x$ 的数量恰好就是 $\varphi(y)$ 。

综上所述，本题的答案就是 $3 + 2*\sum_{i = 2}^{N}\varphi (i)$ 。我们要做的事情就是求出 $2\sim N$ 中每个数的欧拉函数。

利用Eratosthenes筛法，我们可以按照欧拉函数的计算式，在 $O(N\log N)$ 的时间内求出 $2\sim N$ 中每个数的欧拉函数。

void euler(int n) {  
    for (int i = 2; i <= n; i++) phi[i] = i;  
    for (int i = 2; i <= n; i++)  
        if (phi[i] == i)  
            for (int j = i; j <= n; j++)  
                phi[j] = phi[j] / i * (i - 1);  
}

至此，本题已经得到解决。不过我们还可以进一步优化，利用线性筛法的思想在 $O(N)$ 的时间内快速递推出 $2\sim N$ 中每个数的欧拉函数。

由前面提到的性质4和性质5：

1. 若 $p \mid n$ 且 ${p}^{2} \mid n$ ,则 $\varphi \left( n\right) = \varphi \left( {n/p}\right) * p$ 。

2. 若 $p \mid n$ 但 $p^2 \nmid n$ ，则 $\varphi(n) = \varphi(n / p) * (p - 1)$ 。

在线性筛法中，每个合数 $n$ 只会被它的最小质因子 $p$ 筛一次。我们恰好可以在此时执行上面两条判断，从 $\varphi(n / p)$ 递推到 $\varphi(n)$ 。

int v[MAX_N], prime[MAX_N], phi[MAX_N];  
void euler(int n) {  
    memset(v, 0, sizeof(v)); // 最小质因子  
    m = 0; // 质数数量  
    for (int i = 2; i <= n; i++) {  
        if (v[i] == 0) { // i是质数  
            v[i] = i, prime[++m] = i;  
            phi[i] = i - 1;  
        }  
    // 给当前的数i乘上一个质因子  
    for (int j = 1; j <= m; j++) {  
        // i有比prime[j]更小的质因子，或者超出n的范围  
        if (prime[j] > v[i] || prime[j] > n / i) break;  
        // prime[j]是合数i*prime[j]的最小质因子  
        v[i*prime[j]] = prime[j];  
        phi[i*prime[j]] = phi[i]  
        *(i%prime[j] ? prime[j]-1 : prime[j]);  
    }  
}