如果定义在正整数集上的函数 $f(n)$ 满足对于任意一对互素正整数 $n, m$ 都有 $f(n)f(m)=f(nm)$, 那么 $f$ 就叫做积性函数。
积性函数又可以表示为，假设 $n$ 的素因子分解式为 $n=prod_{i=1}^mp_i^{c_i}$, 那么 $f(n)=prod_{i=1}^mg(p_i, c_i)$.
本文讨论的函数满足：$g(p, c)$ 能够快速求单点值，且 $g(x, 1)$ 是关于 $x$ 的低次多项式。
积性函数求和，就是要求出 $sum_{n=1}^N f(n)$.
筛法DP
我们先来看一道简单的例题。
例 求 $n$ 以内素数的个数 $pi(n)$, 其中 $n le 10^{11}$.
解 考虑用动态规划模拟筛法，筛掉最小素因子是 $2$ 的数，然后筛掉最小素因子是 $3$ 的数，以此类推……
于是我们可先预处理 $sqrt n$ 以内的素数，从小到大记作 $p_1, p_2, ldots, p_m$.
记 $p_{min}(x)$ 表示 $x$ 的最小素因子，其中整数 $x>1$; 特别地，$p_{min}(1)=+infty$. 再记 $F(i, j)$ 表示满足 $p_{min}(x)>p_i$ 且 $x le j$ 的正整数 $x$ 的个数，也就是从 $1$ 到 $j$ 中筛掉 $p_1$ 至 $p_i$ 的倍数后剩余的数的个数。
那么合数和 $sqrt n$ 以内的素数会被筛去，所以答案为 $m+F(m, n)-1$.
初值显然为 $F(0, j)=j$, $F(i, 0)=0$.
考虑最小素因子为 $p_i$ 的数，那么它可以表示为 $kp_i$, 其中 $k le leftlfloor{j over p_i} ight floor$, 且 $p_{min}(k)>p_{i-1}$.
所以转移可写为 $F(i, j)=F(i-1, j)-Fleft(i-1, leftlfloor{j over p_i} ight floor ight)$.
这个DP尚停留在暴力阶段，考虑优化。
首先可以加入滚动数组优化。那么可写为：
$F_0(j)=j$
$F_i(j)=F_{i-1}(j)-F_{i-1}left(leftlfloor{j over p_i} ight floor ight)$.
这里，$F_i(j)$ 和 $F_{i-1}(j)$ 共用内存地址，下同。
由于 $leftlfloor{leftlfloor{n/a} ight floor over b} ight floor=leftlfloor{n over ab} ight floor$, 可知所有可能取得的 $j$ 都形如 $leftlfloor{n over a} ight floor$. 当 $j le sqrt n$ 时，$j$ 的取值至多有 $sqrt n$ 种；当 $j>sqrt n$ 时，由于 $a<sqrt n$, $j$ 的取值少于 $sqrt n$ 种。因此，有用的 $j$ 少于 $2sqrt n$ 个，由于 $m=pi(sqrt n)simfrac{n^{0.5}}{ln n}$, 只计算这些 $j$, 就能把时间复杂度降为 $Oleft({n over log n} ight)$, 空间复杂度降为 $O(sqrt n)$.
考虑进一步优化。
根据定义，我们知道若 $j<p_i$, 则 $F_{i-1}(j)=1$.
进一步地，若 $p_i le j<p_i^2$, 则 $F_i(j)=F_{i-1}(j)-1$, 换句话说，$F_i(j)+i=F_{i-1}(j)+(i-1)$.
于是我们改为记录 $F'_i(j)=F_i(j)+i$, 这样，就只需重新计算满足 $p_i^2 le j$ 的 $F'_i(j)$.
那么这里需要计算的状态数有多少呢？注意到，$F'_i(j)$ 需要计算当且仅当 $p_i^2 le j le n$, 也就是每个 $j le n$ 都对应了 $pileft(sqrt j ight)=Oleft(frac{j^{0.5}}{log j} ight)$ 个 $i$.
对于所有可能的 $j$ 求和，得：
$$egin{align}&sum_{j=1}^{lfloorsqrt n floor}Oleft(frac{j^{0.5}}{log j} ight)+sum_{a=1}^{lfloorsqrt n floor}Oleft(frac{lfloor n/a floor^{0.5}}{loglfloor n/a floor} ight)\=&Oleft(sum_{a=1}^{lfloorsqrt n floor}frac{lfloor n/a floor^{0.5}}{loglfloor n/a floor} ight)\=&Oleft(frac{int_{0}^{sqrt n}sqrt{n over x}mathrm dx}{log n} ight)\=&Oleft(frac{n^{0.75}}{log n} ight)end{align}$$
由上可知，时间复杂度降为 $Oleft(frac{n^{0.75}}{log n} ight)$, 空间复杂度为 $O(sqrt n)$.
我们考虑把此例的筛法DP推广到低次多项式上，也就是求 $n$ 以内所有素数 $p$ 的 $g(p, 1)$ 之和：
首先把不同幂次分开来算，假设现在要算的是 $n$ 以内所有素数的 $alpha$ 次方的和。
处理出所有 $sqrt n$ 内的素数，从小到大排列为 $p_1<p_2<cdots<p_m$. 这些素数的 $alpha$ 次方直接算，接下去需要考虑的就是不含 $sqrt n$ 以内素因子的数的 $alpha$ 次方之和，最后扣除 $1$.
记 $F_i(j)$ 表示所有满足 $p_{min}(x)>p_i$ 且 $x le j$ 的所有正整数 $x$ 的 $x^{alpha}$ 之和。
初值 $F_0(j)=sum_{k=1}^jk^{alpha}$, 通过插值求出。
转移 $F_i(j)=F_{i-1}(j)-p_i^{alpha}F_{i-1}left(leftlfloor{j over p_i} ight floor ight)$.
当 $j<p_i$ 时，$F_{i-1}(j)=1$.
进一步地，当 $p_i le j<p_i^2$ 时，$F_i(j)=F_{i-1}(j)-p_i^{alpha}$.
预处理 $sum_{i=1}^kp_i^{alpha}=S_k$, 可得 $F_i(j)+S_i=F_{i-1}(j)+S_{i-1}$, 于是记 $F'_i(j)=F_i(j)+S_i$, 只需计算满足 $p_i^2 le j$ 的 $F'_i(j)$.
因此若不计插值的时间，求一次素数幂和的时间复杂度为 $Oleft(frac{n^{0.75}}{log n} ight)$, 将每个幂和加起来即得到其在素数上的和。
洲阁筛
模仿筛法DP，设 $G_i(j)$ 表示所有满足 $p_{min}(x) ge p_i$ 且 $x le j$ 的正整数 $x$ 的 $f(x)$ 之和。积性函数求和即求 $G_1(n)$.
筛法DP其实对于每个形如 $leftlfloor{n over a} ight floor$ 的 $j$, 求出了不含 $sqrt n$ 以内素因子的数 $x$ 的 $g(x, 1)$ 之和。我们将 $1$ 处的函数值修正，也就是给上述和加上 $1-g(1, 1)$, 得到初值 $G_{m+1}(j)$.
考虑枚举那些 $p_{min}(x)=p_i$ 的数 $x$ 中 $p_i$ 的次数 $c$, 那么可以写为 $x=kp_i^c$, 其中 $k le {j over p_i^c}$, $p_{min}(k)>p_i$.
所以转移为 $G_i(j)=sum_{c=0}^{lfloorlog_{p_i}j floor}g(p_i, c)G_{i+1}left({j over p_i^c} ight)$.
根据定义，当 $j<p_i$ 时，$G_i(j)=1$.
进一步地，当 $p_i le j<p_i^2$ 时，$G_i(j)=G_{i+1}(j)+g(p_i, 1)$.
预处理 $S_i=sum_{k=1}^ig(p_i, 1)$.
假设 $i_0$ 是最大的 $i$ 满足 $i le m$ 且 $p_i le j$. 这可以方便地求出：对 $j le sqrt n$ 预处理 $pi(j)$, 可得 $i_0=egin{cases}pi(j),&j le sqrt n;\m,&j>sqrt n.end{cases}$
因此 $G_i(j)+S_{i-1}=G_{i+1}(j)+S_i=cdots=G_{i_0+1}(j)+S_{i_0}$.
所以当 $p_i le j<p_i^2$ 且 $j le sqrt n$ 时，$G_i(j)=1+S_{pi(j)}-S_{i-1}$; 当 $m<j<p_i^2$ 时，$G_i(j)=G_{m+1}(j)+S_m-S_{i-1}$.
因此只需考虑 $p_i^2 le j$ 的状态，不然可以直接 $O(1)$ 计算得出。
枚举 $(i, j, c)$ 当且仅当 $i le min{sqrt j, sqrt[c]j}$, 由于 $sum_{c=2}^{lfloorlog_2j floor}pileft(sqrt[c]j ight)=Oleft(frac{j^{0.5}}{log j} ight)$, 同筛法DP的复杂度分析可得这一部分的时间复杂度也为 $Oleft(frac{n^{0.75}}{log n} ight)$.
总结
简单来说，洲阁筛分为下列几步：
- 取出所有形如 $leftlfloor{n over a} ight floor$ 的正整数。
- 在 $sqrt n$ 范围内预处理素数、素数个数 $pi(j)$、素数的函数值前缀和。
- 筛法DP求最小素因子较大的数对应的函数值的和。
- 倒序筛法DP求范围内所有正整数的函数值的和。
其时间复杂度为 $Oleft(frac{n^{0.75}}{log n} ight)$, 空间复杂度为 $O(sqrt n)$.
模板题
本题中，$g(x, c)=x oplus c$. 特殊处理 $sqrt n<2$ 的情况，否则对于 $p>sqrt nge2$ 都有 $g(p, 1)=p-1$, 为低次多项式。接下来就可以全盘套用洲阁筛了。
Min_25筛
注意：可能和原版Min_25筛有区别。
我们在洲阁筛的第二步“倒序筛法DP”基础上魔改一下。
设 $G(i, j)$ 表示所有满足 $p_{min}(x) ge p_i$ 且 $x le j$ 的正整数 $x$ 的 $f(x)$ 之和。积性函数求和即求 $G(1, n)$. 初值同洲阁筛。
枚举 $p_{min}(x)=p_k$, 其中 $k ge i$; 再枚举 $x$ 中 $p_k$ 的次数 $c$, 可得：
$$G(i, j)=sum_{k=i}^msum_{c=1}^{lfloorlog_{p_k}j floor}g(p_k, c)Gleft(k+1, leftlfloor{x over p_k^c} ight floor ight)$$
当 $j<p_i$ 时，$G(i, j)=1$. 因此：
$$G(i, j)=sum_{k=i}^msum_{c=1}^{lfloorlog_{p_k}j floor-1}g(p_k, c)Gleft(k+1, leftlfloor{x over p_k^c} ight floor ight)+g(p_k, lfloorlog_{p_k}j floor)$$
对于满足 $p_k^2>j$ 的那些 $k$, 其内部和式仅剩 $g(p_k, 1)$. 因此，如洲阁筛所述定义前缀和 $S_k$, 设 $k_0$ 是最大的满足 $i le k le m$ 且 $p_k^2 le j$ 的整数 $k$（若不存在设为 $i-1$），则可以得到：
$$G(i, j)=sum_{k=i}^{k_0}sum_{c=1}^{lfloorlog_{p_k}j floor-1}g(p_k, c)Gleft(k+1, leftlfloor{x over p_k^c} ight floor ight)+g(p_k, lfloorlog_{p_k}j floor)+S_{min{pi(j), m}}-S_{k_0}$$
递归求解即可。
时间复杂度有不同说法，从 $Oleft(frac{n^{0.75}}{log n} ight)$ 到 $Oleft(frac{n}{log log n} ight)$ 不等。实际上跑得飞快。