数论好困难

符号及基本定义及约定

整除、取模、质数、算术基本定理等的定义。这部分直接 skip 了。

以下无特殊说明则默认变量为正整数，函数为数论函数。

以下用 $\mathbb{P}$ 表示素数集合。

数论函数

定义域为正整数的函数被称为数论函数。

积性函数

若数论函数 $f(x)$ 满足对于任意 $a \bot b$，有 $f(ab) = f(a) f(b)$，则称 $f(x)$ 为积性函数。

若数论函数 $f(x)$ 满足对于任意 $a, b$，有 $f(ab) = f(a) f(b)$，则称 $f(x)$ 为完全积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也是积性函数。

• $h(x) = f(x ^ p)$。
• $h(x) = f ^ p(x)$。
• $h(x) = f(x) g(x)$。
• $h(x) = \sum _ {d \mid x} f(d) g\left(\dfrac{x}{d}\right)$。

设 $x = \prod p _ i ^ {k _ i}$。
对于积性函数 $f(x)$ 有 $f(x) = \prod f(p _ i ^ {k _ i})$。
对于完全积性函数 $f(x)$ 有 $f(x) = \prod f(p _ i) ^ {k _ i}$。

常见积性函数

• 单位函数 $\varepsilon(n) = [n = 1]$。（完全奇性）
• 常数函数 $1(n) = 1$。（完全奇性）
• 除数函数 $\sigma _ k(n) = \sum _ {d | n} d ^ k$。特别地，$\sigma _ 0(n)$ 通常记作 $d(n)$ 或 $\tau(n)$，$\sigma _ 1(n)$ 通常记作 $\sigma(n)$。
• 欧拉函数和莫比乌斯函数后面会说。

素数

素数计数函数：$\pi(n) = \sum\limits _ {i = 1} ^ n [i \in \mathbb{P}]$。

结论：$\pi(n) \sim \dfrac{n}{\ln n}$。

Miller-Rabin 素性测试

**素性测试（Primality test）**是一类在 **不对给定数字进行素数分解（prime factorization）**的情况下，测试其是否为素数的算法。——OI Wiki

素性测试有两种，一种为确定性测试，能完全确定一个数是否为素数；另一种为概率性测试，通常比确定性测试快得多，但有极小概率将合数判断为素数。

Fermat 素性测试

利用费马小定理（$\forall p \in \mathbb{P}, a \bot p, a ^ {p - 1} \equiv 1 \pmod{p}$，后面会展开说明），不断选取 $a \in [2, n)$ 并检验是否满足 $a ^ {n - 1} \equiv 1 \pmod{n}$。

若对于合数 $n$，满足对于任意 $a \bot n$，有 $a ^ {n - 1} \equiv 1\pmod{n}$，则称之为卡迈克尔数（Carmichael Number），又称费马伪素数。

卡迈克尔数是无穷的。（见 OEIS A006931（拥有 $n$ 个质因子的最小的卡迈克尔数））

二次探测定理

对于 $p \in \mathbb{P}$，方程 $x ^ 2 \equiv 1 \pmod{p}$ 的解为 $x \equiv 1 \pmod{p}$ 或 $x \equiv p - 1 \pmod{p}$。

实现

考虑结合 Fermat 素性测试和二次探测定理。

首先特判掉 $n$ 为偶数的情况，然后有 $n - 1$ 为偶数。

所以 $a ^ {n - 1} = \left(a ^ {\frac{n - 1}{2}}\right) ^ 2 \equiv 1 \pmod{n}$。若 $n$ 为素数则必须满足 $a ^ {\frac{n - 1}{2}}$ 为 $1$ 或 $n - 1$。

于是，我们将 $n - 1$ 拆分为 $u \times 2 ^ t$，然后令 $x = a ^ u$，不断平方至多 $t$ 次，判断过程是否出现 $x = n - 1$ 即可。

在 OI 中，$a$ 一般取$\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$ 或 $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$（前 $12$ 个质数）即可解决 $[2, 2 ^ {64})$ 以内的问题。

注意要取遍里面的数（模 $n$ 意义下）而不是只取 $\le n$ 的。若模 $n$ 意义下为 $0$ 则直接跳过。

// Problem: SPOJ-PON - Prime or Not.
// Link: https://www.spoj.com/problems/PON/

// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int prime[] = {2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37};

int T;
long long n;

long long power(long long a, long long b, long long mod) {
	long long ans = 1;
	while (b) {
		if (b & 1) ans = (__int128)ans * a % mod;
		a = (__int128)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
int Miller_Rabin(long long n) {
	if (n == 1) return 0;
	if (n == 2) return 1;
	if (n % 2 == 0) return 0;
	long long u = n - 1, t = 0;
	while (u % 2 == 0) u /= 2, t++;
	for (int i = 0; i < 12; i++) {
		if (prime[i] % n == 0) continue;
		long long x = power(prime[i] % n, u, n);
		if (x == 1) continue;
		int flag = 0;
		for (int j = 1; j <= t; j++) {
			if (x == n - 1) {flag = 1; break;}
			x = (__int128)x * x % n;
		}
		if (!flag) return 0;
	}
	return 1;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		puts(Miller_Rabin(n) ? "YES" : "NO");
	}
	return 0;
}

对 $n$ 进行 $k$ 轮测试的时间复杂度为 $O(k \log ^3 n)$，可以使用 FFT 优化到 $O(k \log ^ 2 n \log \log n \log \log \log n)$。

数论分块

用于快速求解 $\sum _ {i = 1} ^ n f(i) g\left(\dfrac{n}{i}\right)$ 式的式子。

结论 1：$\forall n \in \mathbb{N _ +}, \left|\left\lfloor\dfrac{n}{d}\right\rfloor \mid d \in \mathbb{N _ +}, d \le n\right| \le \lfloor2\sqrt{n}\rfloor$。

证明：

对于 $d \le \sqrt{n}$，$\left\lfloor\dfrac{n}{d}\right\rfloor$ 显然只有 $\sqrt{n}$ 种取值。

对于 $d > \sqrt{n}$，有 $\dfrac{n}{d} \le \sqrt{n}$，所以 $\left\lfloor\dfrac{n}{d}\right\rfloor$ 也只有 $\sqrt{n}$ 种取值。

故总共只有 $\lfloor2\sqrt{n}\rfloor$ 种取值。

证毕。

结论 2：对于任意 $n, i, i \le n$，满足 $\left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor$ 的最大的 $j$ 为 $\left\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor$。

证明：

$\left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor \le \dfrac{n}{j} \implies j \le \dfrac{n}{\lfloor\frac{n}{i}\rfloor}$。由于 $j$ 要最大，所以 $j = \left\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor$。证毕。

由于 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 值相同的 $i$ 是连续的，且一共只有 $O(\sqrt{n})$ 种取值，故我们可以枚举所有 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 的取值和对应的 $i$ 的区间，如果能快速求出 $f$ 的前缀和，就可以通过 $O(\sqrt{n})$ 次计算得到结果。

伪代码大概长这样：

$$\begin{array}{l|l} 1 & \textbf{Method.} \\ 2 & \textbf{Function } \text{sqrtDecomposition}()\\ 3 & \qquad l \gets 1 \\ 4 & \qquad r \gets 0 \\ 5 & \qquad \textbf{while } l \le n \textbf{ do:} \\ 6 & \qquad \qquad r \gets \left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor \\ 7 & \qquad \qquad ans \gets ans + \left(\sum\limits _ {i = l} ^ r f(i)\right) \cdot g\left(\left\lfloor\dfrac{n}{l}\right\rfloor\right) \\ 8 & \qquad \qquad l \gets r + 1 \\ 9 & \qquad \textbf{endwhile} \\ 10 & \qquad \textbf{return } ans \\ 11 & \textbf{Endfunction} \end{array}$$

若计算 $f$ 的前缀和和 $g$ 的某个点值都是 $O(1)$ 的，则时间复杂度为 $O(\sqrt{n})$。