对于数论函数 $f$ 定义前缀和 $S_f(n)=\sum_{i=1}^nf(i)$。

如果有两个数论函数 $f,g$ 满足我们可以快速计算 $S_g$ 和 $S_{f*g}$，可以通过杜教筛快速求出 $S_f(n)$。

$$\displaylines{\begin{aligned} S_{f*g}(n)=&\sum_{i=1}^n\sum_{d|i}g(d)f\left(\frac id\right)\\ =&\sum_{d=1}^ng(d)\sum_{k=1}^{\lfloor\frac nd\rfloor}f(k)\\ =&\sum_{d=1}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) \end{aligned} }$$

于是有

$$\displaylines{g(1)S_f(n)=S_{f*g}(n)-\sum_{d=2}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) }$$

直接利用该式记忆化地递归求解，因为

$$\displaylines{\left\lfloor\frac{\lfloor\frac n{d_1}\rfloor}{d_2}\right\rfloor=\left\lfloor\frac n{d_1d_2}\right\rfloor }$$

所以我们只在所有 $\lfloor\frac nd\rfloor$ 处求了 $S_f$ 的值（其中 $d$ 是 $[1,n]$ 内的整数），每次求值使用整除分块，将 $d$ 以 $\sqrt n$ 为界分开考虑，总复杂度如下：

$$\displaylines{\begin{aligned} &O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt\frac ni\right)\\ =&O\left(\int_0^{\sqrt n}\sqrt x\mathrm dx+\int_0^{\sqrt n}\sqrt\frac nx\mathrm dx\right)\\ =&O\left(\left.x^{\frac32}\right|_0^{\sqrt n}+\left.\sqrt{nx}\right|_0^{\sqrt n}\right)\\ =&O\left(n^\frac34\right) \end{aligned} }$$

如果 $f$ 可以通过线性筛预处理出不超过 $K$ 的 $S_f$ 值，复杂度可以进一步优化。因为只求所有不超过 $\sqrt n$ 处的 $S_f$ 值已经达到了 $O(n^\frac34)$ 的复杂度，所以想要优化复杂度，$K$ 至少为 $\sqrt n$。所以有

$$\displaylines{\begin{aligned} &O\left(K+\sum_{i=1}^\frac nK\sqrt\frac ni\right)\\ =&O\left(K+\left.\sqrt{nx}\right|_0^{\frac nK}\right)\\ =&O\left(K+nK^{-\frac12}\right) \end{aligned} }$$

$K=O(n^\frac 23)$ 时复杂度平衡，为 $O(n^\frac 23)$。

素性测试

二次探测定理：对于质数 $p$，方程 $x^2\equiv1\pmod p$ 的解只有 $x\equiv\pm1\pmod p$。

证明：$(x+1)(x-1)\equiv x^2-1\equiv1\pmod p$，于是 $p\mid(x+1)(x-1)$。由于 $p$ 是质数，$p\mid x+1$ 或 $p\mid x-1$ 至少有一个成立。$\square$

这意味着，如果我们想判定 $p$ 的素性，我们可以尝试找出 $x\not\equiv\pm1\pmod p$ 而 $x^2\equiv1\pmod p$ 的 $x$。一旦我们找出了一个这样的 $x$，$p$ 一定不是素数。而在经过大量检测后没有找到这样的 $x$，我们即宣称 $p$ 是素数（并且我们确实能够证明这样做的正确性）。

考察费马小定理 $a^{p-1}\equiv1\pmod p$，其中 $p$ 为素数。我们将 $p-1$ 表示为 $2^sd$，其中 $d$ 为奇数。

如果我们任选一个 $(0,p)$ 内的整数作为底数 $a$，将 $d,2d,4d,\cdots,2^{s-1}d$ 分别代入 $x$，如果有 $a^{2^kd}\not\equiv\pm1\pmod p$ 而 $a^{2^{k+1}d}\equiv1\pmod p$ 则说明 $p$ 不是质数。如果 $a^{p-1}\not\equiv1\pmod p$ 也说明 $p$ 不是质数。

可以证明，能够将一个非质数 $n$ 判别出来的底数 $a$ 至少有 $\left\lfloor\frac{n-1}2\right\rfloor$ 个。也即在 $(0,n)$ 中随机选取 $a$，将非质数判别为质数的概率不超过 $\frac12$，那么随机选择多个底数分别判断即可达到较高正确率。

如果广义黎曼猜想成立，只需以 $[2,\min\{n-2,\lfloor2\ln^2n\rfloor\}]$ 的所有数分别作为底数 $a$ 进行探测，即可确定 $n$ 的素性而不依赖于概率分析。而对于 OI 中常见的 $[1,2^{64})$ 中的所有数，只用不超过 $40$ 的 $12$ 个质数即可。

分解质因数

对于合数 $n$，通过枚举获取 $n$ 的因数是困难的，可以考虑以一定的方式生成一些 $k$，通过求 $\gcd(n,k)$ 获取 $n$ 的非平凡因子。那么我们要做的就是尽量减小 $\gcd(n,k)$ 为 $1$ 或 $n$ 的概率。

考虑数列 $a_0=0,a_i=(a_{i-1}^2+c)\bmod n$，其中 $c$ 是 $(1,n)$ 内的任意整数。设 $n$ 有某一因子 $k$。显然数列 $\{a_i\bmod k\}$ 一定会在有限项内进入循环。而 $a_i\bmod k=a_j\bmod k$ 意味着 $k\mid a_i-a_j$，此时如果 $n\nmid a_i-a_j$ 的话，$\gcd(n,a_i-a_j)$ 即为 $n$ 的一个非平凡因子，否则分解失败。

具体实现有两种。

第一种实现本质上是 Floyd 判环算法，从小到大枚举 $i$，如果某次 $k=\gcd(a_i-a_{2i},n)$ 不为 $1$，说明数列 $\{a_n\bmod k\}$ 在第 $i$ 项之前已进入循环。

第二种实现是利用倍增，将两个指针 $s,t$ 初始设为 $0$，第 $i$ 轮 $t$ 向后移动 $2^{i-1}$ 步，每步之后检查 $\gcd(n,s-t)$，该轮结束后将 $s$ 赋为 $t$。为了进一步优化常数，每 $127$ 步检验近 $127$ 步中 $s-t$ 的累乘结果。实验表明，$127$ 是一个很好的参数，过小会导致求 $\gcd$ 的次数较多，过大会导致累乘结果得到 $0$ 的概率过大，频繁失败。

两种实现的期望复杂度均为 $O(m\log a)$。其中 $m$ 为 $\min_{d|n}\#\{a_i\bmod d\mid i\in\mathbb N\}$ 在 $c$ 均匀随机时的期望。首先该值一定小于 $\#\{a_i\bmod k\mid i\in\mathbb N\}$，其中 $k$ 为 $n$ 的最小质因子。

那么期望多少项 $\{a_i\bmod k\}$ 会开始循环呢？首先我们发现该数列在 $(1,k)$ 内的分布较为均匀（这也是选择 $(x^2+c)\bmod n$ 来生成数列下一项的原因），所以该数列进入循环的项数等同于不断在 $k-1$ 个元素中均匀随机选取，第一次取到已经出现过的数的期望次数。

在 $n$ 个元素中进行 $t$ 次选择结果两两不同的概率为 $P=\prod_{i=0}^{t-1}\frac{n-i}n$，由 $1+x\le e^x$ 有

$$\displaylines{P=\prod_{i=0}^{t-1}\frac{n-i}n\le\prod_{i=0}^{t-1}\exp\left(-\frac in\right)=\exp\left(-\frac{t(t-1)}{2n}\right) }$$

于是对于 $p\in(0,1)$，

$$\displaylines{P\le p\Longleftarrow\exp\left(-\frac{t(t-1)}{2n}\right)\le p\iff t(t-1)\ge-2n\ln p\Longleftarrow t\ge\sqrt{-2n\ln p} }$$

将 $t$ 次选取看作一次实验，根据独立随机试验的结论，这样的实验失败一次的期望次数为 $\frac1{1-p}$，故在 $k-1$ 个元素中随机选取，直到得到相同元素的期望次数不超过

$$\displaylines{\frac1{1-p}\sqrt{-2(k-1)\ln p}=O(\sqrt k) }$$

于是该算法的复杂度为 $O(m\log a)=O(\sqrt k\log a)=O(\sqrt[4]n\log a)$。

令 $b_i=\gcd(a_1,a_2,\cdots,a_3)$， 不难发现 $b_{i+1}\mid b_i$。

于是我们设 $f_x$ 为将序列 $a$ 中所有 $x$ 的倍数重排得到序列 $t_1,t_2,\cdots,t_m$ 之后，$\sum_{i=1}^m\gcd(t_1,t_2,\cdots,t_i)$ 的最大值。

那么显然 $f$ 在 $x$ 处的值只会从它的所有倍数 $kx$ 处转移而来，并且 $f_{kx}$ 对应的最优的序列一定是 $f_x$ 对应的最优的序列的前缀。

转移方程为

$$\displaylines{f_x=\max_{kx\le\max\{a\}}\left\{f_{kx}+\sum_{i=1}^n[x\mid a_i\land kx\not\mid a_i]\right\} }$$

这样转移是 $O(n\log n)$ 的。

考虑到对于合数 $k=pq$（$p,q$ 不为 $1$），$f_{kx}\to f_{px}\to f_{qx}$ 的转移不比 $f_{kx}\to f_{x}$ 劣，所以实际上可以仅枚举所有质数 $k$ 进行转移。

数论函数定义为定义域为整数，值域为整数的函数。

常见的数论函数：

• 单位函数 $\varepsilon(n)=[n=1]$
• 常数函数 $k(n)=k$
• 恒等函数 $\mathrm{id}_k(n)=n^k$，$\mathrm{id}_0$ 简记作 $\mathrm{id}$
• 除数函数 $\sigma_k(n)=\sum_{d|n}d^k$，$\sigma_0$ 简记作 $d$，$\sigma_1$ 简记作 $\sigma$
• 欧拉函数 $\varphi(n)$ 表示 $[1,n]$ 中与 $n$ 互质的数
• 莫比乌斯函数 $\mu(n)$

函数 $f$ 是积性函数当且仅当 $f(1)=1$，且对于任意互质的 $x,y$ 都有 $f(xy)=f(x)f(y)$。

函数 $f$ 是完全积性函数当且仅当 $f(1)=1$，且对于任意 $x,y$ 都有 $f(xy)=f(x)f(y)$。

Dirichlet 卷积

对于两个数论函数 $f,g$，$f$ 与 $g$ 的 Dirichlet 卷积定义为

$$\displaylines{(f*g)(n)=\sum_{d|n}f(d)g(\frac nd) }$$

Dirichlet 卷积具有交换律、结合律，$\varepsilon$ 为 Dirichlet 卷积的单位元。

任何 $1$ 处点值非 $0$ 的数论函数都存在 Dirichlet 卷积逆。

积性函数的 Dirichlet 卷积是积性函数，积性函数的 Dirichlet 卷积逆也是积性函数。

莫比乌斯函数

定义莫比乌斯函数

$$\displaylines{\mu(n)=\begin{cases}0&(\exists x>1,x^2|n)\\(-1)^{\omega(n)}&(\text{Otherwise})\end{cases} }$$

莫比乌斯函数与 $1$ 互为 Dirichlet 卷积逆，即 $\mu*1=\varepsilon$。

证明：

$$\displaylines{(\mu*1)(n)=\sum_{d|n}\mu(d) }$$

考虑到右式只有当 $d$ 不含平方因子时 $\mu(d)$ 才非 $0$。

设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$。显然

$$\displaylines{\begin{aligned} (\mu*1)(n) &=\sum_{T\subseteq\{p_1,p_2,\cdots p_n\}}\mu\left(\prod_{t\in T}t\right)\\ &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\\ &=\sum_{k=0}^n\binom nk(-1)^k\\ &=(1-1)^n\\ &=\varepsilon(n)\qquad\Box \end{aligned} }$$

数论函数的常见性质

$\varphi*1=\mathrm{id}$，也即 $\sum_{d|n}\varphi(d)=n$。

证明：考虑构造 $x\in[1,n]$ 到 $\{(d,x):d|n,\gcd(x,d)=1\}$ 的映射

$$\displaylines{f:x\mapsto\left(\frac n{\gcd(x,n)},\frac x{\gcd(x,n)}\right) }$$

不难发现这是一个双射。$\Box$

$\varphi=\mu*\mathrm{id}$，也即 $\sum_{d=1}^n[\gcd(n,x)=1]=\sum_{d|n}\mu(d)\cdot\dfrac nd$。

证明：设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$，由容斥原理

$$\displaylines{\begin{aligned} \sum_{d=1}^n[\gcd(d,n)=1] &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\cdot\frac n{\prod_{t\in T}t}\\ &=\sum_{d|n}\mu(d)\cdot\frac nd\qquad\Box \end{aligned} }$$

设 $n={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_n}^{\alpha_n}$，其中 $p$ 两两不同，$\alpha_i\ge1$。有

$$\displaylines{\varphi(n)=n\prod_{i=1}^n1-\frac1{p_i} }$$

证明：类似上一个结论，运用容斥原理有

$$\displaylines{\begin{aligned} \sum_{d=1}^n[\gcd(d,n)=1] &=\sum_{T\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|T|}\cdot\frac n{\prod_{t\in T}t}\\ &=n\sum_{T\subseteq\{p_1,p_2\cdots,p_n\}}\prod_{t\in T}-\frac1t\\ &=n\prod_{i=1}^n(1-\frac1{p_i}) \end{aligned} }$$