如果你以前从未接触过数论，AoPS 是一个很好的起点。

学习资料

质因数分解

若非负整数 $b$ 能被正整数 $a$ 整除，即存在某个整数 $k$ 使得 $b=ka$， 则称 $a$ 是 $b$ 的因数（或约数）。若整数 $n>1$ 的正因数只有 $1$ 和 $n$，则称 $n$ 为质数。大于 $1$ 且不是质数的整数称为合数。

每个正整数都有唯一的质因数分解，即可以按照下式唯一地写成若干质数的乘积：

其中 $p_i$ 是互不相同的质数，$a_i$ 是正整数。

下面讨论如何求任意正整数的质因数分解。

Copy
from typing import List


def factor(n: int) -> List[int]:
	ret = []
	i = 2
	while i * i <= n:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret

该算法的时间复杂度为 $\mathcal{O}(\sqrt n)$，因为 for 循环最多检查 $\sqrt n$ 个候选因数。虽然其中还有一个 while 循环，但每次用 $i$ 除去 $n$ 都会迅速减小 $n$，从而让外层循环更早结束，并不会增加渐进复杂度。

以 $n=252$ 为例，算法执行过程如下：

此时 for 循环结束，因为 $i=3$ 已经大于 $\lfloor\sqrt7\rfloor$。最后把 $7$ 加入因数列表，否则它不会在循环中被加入。最终得到质因数分解 $\{2,2,3,3,7\}$。

题解——Counting Divisors

最直接的做法就是按题意计算：对每个 $x$，在 $\mathcal{O}(\sqrt x)$ 时间内 求出它的因数个数。

Copy
ans = []
for _ in range(int(input())):
	div_num = 0
	x = int(input())
	i = 1
	while i * i <= x:
		if x % i == 0:
			div_num += 1 if i**2 == x else 2
		i += 1
	ans.append(div_num)

print("\n".join(str(i) for i in ans))

这个解法的时间复杂度为 $\mathcal{O}(n\sqrt x)$，刚好足以通过。不过，我们 还可以把它优化到 $\mathcal{O}((x+n)\log x)$。

首先来看质因数分解的一个重要性质。设：

那么 $x$ 的因数个数就是 $(a_1+1)(a_2+1)\cdots(a_k+1)$。

这是因为在 $x$ 的任意因数中，$p_i$ 的指数只能取 $[0,a_i]$ 中的整数； 不同的指数选择会产生不同的因数，因此每个 $p_i$ 都为乘积贡献 $a_i+1$ 种选择。

$x$ 最多有 $\mathcal{O}(\log x)$ 个不同质因数。因此，只要能高效求出 $x$ 的质因数分解，就可以利用上述性质在 $\mathcal{O}(\log x)$ 时间内回答一次 询问，而不再需要 $\mathcal{O}(\sqrt x)$。

下面介绍如何用 $\mathcal{O}(x\log x)$ 的预处理，使每次质因数分解只需 $\mathcal{O}(\log x)$ 时间：

1. 对每个 $k\le 10^6$，找出任意一个能整除 $k$ 的质数。可以使用 Sieve of Eratosthenes ，其复杂度为 $\mathcal{O}(n\log n)$，其中 $n$ 是考虑的最大值。筛法也有 线性时间版本，但这里并不需要。
2. 不断用预处理出的质因数去除 $x$，直到 $x=1$，即可得到完整的质因数分解。

这一方法的实现如下：

Copy
MAX_N = 10**6

# max_div[i] contains the largest prime that can go into i
max_div = [0 for _ in range(MAX_N + 1)]
for i in range(2, MAX_N + 1):
	if max_div[i] == 0:
		for j in range(i, MAX_N + 1, i):
			max_div[j] = i

ans = []

最大公因数与最小公倍数

最大公因数

两个整数 $a,b$ 的最大公因数（GCD），是同时作为二者因数的最大整数。 求两个非负整数的最大公因数时，可以使用欧几里得算法：

该算法可以递归实现如下：

Copy
def gcd(a: int, b: int) -> int:
	return a if b == 0 else gcd(b, a % b)

该函数的复杂度为 $\mathcal{O}(\log ab)$，因为 $a\le b\implies b\pmod a<\frac b2$。

欧几里得算法的最坏情况发生在 $a,b$ 是相邻斐波那契数 $F_n,F_{n+1}$ 时。 此时算法会依次计算 $\gcd(F_n, F_{n + 1}) = \gcd(F_{n - 1}, F_n) = \dots = \gcd(0, F_1)$. ，总共需要 $n+1$ 次调用，与 $\log(F_nF_{n+1})$ 成正比。

最小公倍数

两个整数 $a,b$ 的**最小公倍数（LCM）**是能同时被二者整除的最小正整数。 它可以利用最大公因数计算：

这两种运算都满足结合律。因此计算多个数的 GCD 或 LCM 时，可以按任意顺序 每次合并两个数。例如：

欧拉函数

性质

欧拉函数记作 $\phi(n)$，表示区间 $[1,n]$ 中与 $n$ 互质的正整数个数。 若 $\gcd(a,b)=1$，则称 $a,b$ 互质。

前 20 个正整数的 $\phi(n)$ 如下：

欧拉函数是积性函数：当 $\gcd(n,m)=1$ 时， $\phi(nm)=\phi(n)\phi(m)$。例如 $\phi(15)=\phi(3\cdot5)=\phi(3)\phi(5)=2\cdot4=8$。

来看 $\phi(n)$ 的几个特殊情况：

• 若 $n$ 是质数，则 $\phi(n)=n-1$，因为所有 $1\le x<n$ 都满足 $\gcd(n,x)=1$；
• 若 $n=p^q$ 是质数幂，其中 $p$ 为质数且 $q\ge1$，则恰有 $p^{q-1}$ 个数 能被 $p$ 整除，因此 $\phi(p^q)=p^{q} - p^{q-1} = p^{q-1}(p - 1)$

利用积性和上述质数幂公式，可以由 $n$ 的质因数分解计算 $\phi(n)$。设 $n=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}$，其中 $p_i$ 是 $n$ 的质因数，则：

下面的实现在 $\mathcal{O}(\sqrt n)$ 时间内分解质因数。ans -= ans / p 可能不太直观：设 $ans=p^qx$，其中 $p$ 是质因数，$x$ 是其余部分。减去 $ans/p=p^{q-1}x$ 后得到 $p^qx-p^{q-1}x=p^{q-1}x(p-1)$，恰好对应上面的欧拉函数公式。

Copy
def phi(n: int) -> int:
	ans = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n //= p
			ans -= ans // p
		p += 1

	if n > 1:
		ans -= ans // n

	return ans

题目中经常需要预处理 $1$ 到 $n$ 的所有欧拉函数值，此时逐个分解并不高效。 可以采用与埃氏筛相同的思想，时间复杂度为 $\mathcal{O}(N\log\log N)$。

Copy
def precompute():
	for i in range(1, MAX_N):
		phi[i] = i

	for i in range(2, MAX_N):
		# If i is prime
		if phi[i] == i:
			for j in range(i, MAX_N, i):
				phi[j] -= phi[j] // i

题解

题目要求计算所有满足 $1\le i<j\le n$ 的数对 $(i,j)$ 的 GCD 之和：

定义辅助函数 $f(n)$，表示第二个元素固定为 $n$ 时的 GCD 之和：

该函数对所有 $i\le n$ 的 $\gcd(i,n)$ 求和。当 $\gcd(i,n)=d$ 时，必有 $d\mid n$ 且 $\gcd(i/d,n/d)=1$。满足条件的 $i$ 的个数为 $\phi(n/d)$。因此可以把 $f(n)$ 改写为对 $n$ 的因数求和：

我们可以高效计算所有 $n\le10^6$ 的 $f(n)$。不必逐个分解质因数，只需枚举 每个可能的因数 $i$，再更新它的所有倍数 $j$。对固定的 $i$，向每个倍数 $j$ 的 $f(j)$ 中加入贡献 $i\phi(j/i)$。

最后，题目只统计 $i<j$。而 $f(j)$ 包含 $i=j$ 的情况（此时 $\gcd(j,j)=j$），必须将其减去。因此答案是调整后数值的前缀和：

该预处理的总复杂度由调和级数界定： $\sum_{i=1}^{N} \frac{N}{i} \approx N \ln N$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_N = 1e6;

ll phi[MAX_N + 1];
ll f[MAX_N + 1];
ll sum[MAX_N + 1];

int main() {

练习题