这篇文章介绍一下数论，积性函数求和，以及杜教筛，powerful number 筛，min25 三种筛法
在这之前，我们先来介绍一下一些有趣的东西

Bell series

贝尔级数，对于一个数论函数 \(f\) 和质数 \(p\)，定义
\(f_p(x)=\sum_{n\ge 0}f(p^n)x^n\)
对于两个数论函数 \(f,g\) 的狄利克雷卷积，不妨设为 \(h\)，有 \(h_p(x)=f_p(x)g_p(x)\)
对于完全积性函数，有 \(f_p(x)=\frac 1{1-f(p)x}\)
对于常见的数论函数：
\(\mu_p(x) =1-x\)
\((Id_k)_p(x)=\frac 1{1-p^kx},I_p(x)=\frac 1{1-x}\)
\(\varphi(x)_p=1+\sum_{n\ge 1}p^{n-1}(p-1)x^n=1+\sum_{n\ge 1}p^nx^{n}-\sum_{n\ge 0}p^nx^{n+1}=\frac{1-x}{1-px}\)
\((\sigma_k)_p(x)=\sum_{n\ge 0} \Big(\sum_{i=0}^n p^{ik}\Big) x^n=\sum_{n\ge 0} \frac{1-p^{k(n+1)}}{1-p^k} x^n=\\ \frac{1}{1-p^k}(\sum_{n\ge 0}x^n-p^k\sum_{n\ge 0}p^{kn}x^n)=\frac{1}{1-p^k}(\frac 1{1-x}-p^k\frac 1{1-p^kx})=\frac{1}{(1-x)(1-p^kx)}\)
我们可以自然的发现，\(\mu\times I=\epsilon,\varphi = \mu\times Id,\sigma_k=Id_k\times I\)

Dirichlet GF

介绍一下狄利克雷生成函数
对于数列 \(\{f_1,\dots\}\)，其狄利克雷生成函数为：
\(f(s)=\sum_{n\ge 1} \frac{f_n}{n^s}\)
黎曼 zeta 函数：\(\zeta(s)=\sum_{n\ge 1}\frac 1{n^s}\)
\(\zeta(s)=\prod_p \sum_{e\ge 0}\frac{1}{p^{es}}=\prod_p \frac 1{1-p^{-s}}\)
那么我们又有有趣的结论了
\(\mu(s)=\prod_p (1-p^{-s})=\frac 1{\zeta(s)}\)
\(Id_k(s)=\sum_{n\ge 1}\frac{1}{n^{s-k}}=\zeta(s-k)\)
\(\varphi(s)=\prod_p \sum_{e\ge 0}\frac{p^{e}}{p^{es}}-\sum_{e\ge 0}\frac{p^{e}}{p^{(e+1)s}}=(1-p^{-s})\zeta(s-1)=\frac{\zeta(s-1)}{\zeta(s)}\)

杜教筛

我们对一个 \(N\)，称 \(N,\lfloor\frac N2\rfloor，\dots,1\) 为好位置
对于函数 \(F,G\)，若我们知道 \(F,G\) 好位置上的前缀和，我们可以在 \(N^{2/3}\) 的时间算出 \((F\times G^{-1})\) 在好位置的前缀和
考虑对 \(F\times G^{-1}\) 卷上 \(G\)，那么有 \(\sum_{i=1}^N F_i=\sum_{i=1}^N \sum_{d\mid i}(F\times G^{-1})_d G_{\frac id}=\sum_{d=1}^N G_d \sum_{i=1}^{\frac Nd} (F\times G^{-1})_i\)
若要求 \((F\times G)\) 的前缀和，就更简单了，即 \(\sum_{i=1}^N F_i\sum_{d\le \frac Ni}G_d\)
给我们的启示是，若我们要求 \(H\) 的前缀和，我们需要找到 \(H=F\times G\)

Powerful Number

我们现在要求积性函数 \(F\) 的前缀和，\(p^k\) 处的点值是 \(f(k)\)
我们构造一个数论函数 \(G\)（我们要知道 \(G\) 的好位置的值），那么考虑让 \(F=G\times H\)
附加条件是 \(g(1)=f(1)\)，即质数处取值相同，那么我们设 \(H\times G=F\)
有 \(h(1)g(0)+h(0)g(1)=f(1)\)，即 \(h(1)=0\)，而 \(H\) 是积性函数，故 \(H\) 有值的只有 \(x^2y^3\) 这种数，是 \(O(\sqrt n)\) 的
我们将 \(h(i)\) 的值算出来过后（\(O(\log^2 N)\)）爆搜，那么 \(\sum F_i=\sum_{n}H_n\sum_{i\le \frac Nn} G_i\)

Min_25

Part 1

第一部分是对所有好位置算 \(\sum_{p\le n} f(p)\) 即质数处的取值，设 \(small(i)\) 表示 \(i\) 的最小质因子，\(big(i)\) 表示最大的
设 \(H_{i,j}=\sum_{k\le i,small(k)\ge j\mid k=1\mid k\in Prime} f(k)\)，转移如下：
\(H_{i,j}=H_{i,j-1}-f(p)(H_{\lfloor \frac i {p_j} \rfloor, j-1}-H_{p_j-1,j-1})\)，这一部分是 \(O(\frac {N^{3/4}}{\log N})\)

Part 2

接下来要算前缀和，即

我们设 \(S(N,m)=\sum_{2\le x\le N,small(x)>p}f(x)\Big),h_n=\sum_{2\le p\le n,p\in Prime} f(p)\)
那么有 \(S(N,m)=\sum_{m<p\le \sqrt n,e\ge 1}f(p^e)([e>1]+S(\frac{N}{p^e},p))+h_N-h_m\)
来证明暴力递归的复杂度，注意到次数就是我们算 \(h_n-h_m\) 的次数，注意到算到一个 \(h_n-h_m\)，前一步乘了一个 \(m^e\) 过来
故这个 \(m\) 的次数其实是所有 \(big(i)=m\) 的个数，那么我们的次数事实上是 \(i\times big(i)\le N\) 的个数
当 \(N\le 10^{13}\) 时，若 \(big(n)\le N^{\frac 14}\)，打表得知对每个 \(m\le N^{\frac 14}\)，\(big(n)=m\) 的个数是 \(O(\sqrt n)\) 的
若 \(big(n)>N^{\frac 14}\)，则枚举 \(big(n)\)，得到 \(\sum_{p\ge N^{\frac 14}}\frac{N}{p^2}\)，得到复杂度为 \(O(\frac {N^{\frac 34}}{\log N})\)

Min_25 Plus

定义 \(\pi_k(n)\) 表示素数 \(k\) 次幂的前缀和
定义 \(\phi_k(n,a)=\sum_{i=1}^n[small(i)>p_a]i^k\)，记 \(cnt_i\) 表示不同质因子个数
定义 \(P_{s,k}(n,a)=\sum_{i=1}^n[small(i)>p_a,cnt_i=s]i^k\)
诡异的做法开始了，设 \(x^{1/3}\le B=p_a\le x^{1/2}\)
那么 \(\phi_k(x,a)=P_{0,k}(x,a)+P_{1,k}(x,a)+P_{2,k}(x,a)=1+\pi_k(x)-\pi_k(p_a)+P_{2,k}(x,a)\)
所以只需要算 \(\pi (x)=\phi(x,a)-P_{2}(x,a)+\pi(p_a)\)（省略 \(k\)）
\(\pi_k(p_a)\) \(O(B)\) 计算即可

计算 \(P_{2}(x,a)\)

有 \(P_2(x,a)=\sum_{n\le x,n=pq,p_a<p\le q\le \frac xp,p,q\in Prime} n^k\)
此时注意到 \(p,q\le \frac xB\)，故我们枚举 \(p\)，然后做前缀和就可以了，复杂度 \(O(\frac xB)\)

计算 \(\phi(x,a)\)

我们知道 \(\phi(x,a)=\phi_k(x,a-1)-p^k\phi(\lfloor\frac{x}{p_a}\rfloor,a-1)\)
利用容斥得到：\(\phi(x,a)=\sum_{big(n)\le p_a,small(n)>p_b}\mu(n)n^k\phi(\lfloor \frac {x}{n}\rfloor,b)=\sum_{big(n)\le p_a} \mu(n)n^k\lfloor \frac {x}{n}\rfloor\)
暴力统计 \(n\le B\) 的贡献，那么就是要求 \(\sum_{n>B,big(n)\le p_a}\mu(n)n^k\lfloor \frac {x}{n}\rfloor\)
考虑这么一个做法，我们从大到小 \(DFS\) \(n\) 的质因子，当 \(n>B\) 的时候停止，可以得到
\(\sum_{n>B,big(n)\le p_a}\mu(n)n^k\phi(\lfloor \frac {x}{n}\rfloor,small(n)-1)\)
注意到此时相当于 \(n>B\)，但 \(\frac n{small(n)}\le B\)，设 \(p=small(n),m=\frac n{small(n)}\)
那么可以得到，就是算 \(-\sum_{p\le B}\sum_{small(m)>p,m\le B<mp}\mu(m)m^kp^k\phi(\frac x{mp},\pi_0(p)-1)\)

\(p\le \sqrt B\)

对于 \(p\le \sqrt B\)，直接利用递归式算所有 \(\phi(y,p)\)，复杂度 \(O(\frac{\sqrt {xB}}{\log B})\)

\(p>x^{1/3}\)

当 \(p>x^{1/3}\) 时，此时由 \(p>\sqrt B\)，若 \(m\) 为合数，则 \(m>p^2>B\)，没有这样的 \(m\)
那直接枚举 \(\sum_{p\le B}\sum_{q>p,q\le B\le pq} (pq)^k\phi(\frac{x}{pq},\pi_0(p)-1)\)
此时 \(p<\frac x{pq}\)，故 \(\phi(\frac {x}{pq},\pi_0(p)-1)=1\)，\(O(B)\) 算就可以

\(\sqrt B<x\le x^{1/3}\)

当 \(\sqrt B<x\le x^{1/3}\) 时
任然是算 \(\sum_{p\le B}\sum_{q>p,q\le B\le pq} (pq)^k\phi(\frac{x}{pq},\pi_0(p)-1)\)，用定义展开
\(\sum_{p\le B}\sum_{q>p,q\le B\le pq} (pq)^k \sum_{pqr\le x,small(r)\ge p} r^k\\=\sum_{r=1}^{\frac xB} r^k\sum_{\sqrt B<p\le x^{1/3}}\sum_{p<q\le B}(pq)^k[pqr\le x,small(r)\ge p]\\ \sum_{r=1}^{\frac xB}r^k\sum_{\sqrt B<p\le min(small(r),x^{1/3})}p^k\sum_{p<q\le min(\frac{x}{pr},B)}q^k\)
考虑我们要做的事情，对 \(\le \frac xB\) 求出 \(small(r)\)，枚举 \(p\)
此时再枚举 \(c=\frac x{pr}\)，查询有多少 \(r\) 满足 \(small(r)\ge p,\frac x{pr}=c\)，用一个长度为 \(\frac xB\) 的树状数组查个数
对 \(q\) \(O(B)\) 维护一个前缀和
修改次数：由于 \(small(r)\le \sqrt B\) 个可以不用管（不会改），可以证明这样的次数是 \(\frac{x}{B\log x}\) 的（而不是 \(\frac xB\)）
（结论是：对于 \(k,0<\alpha<1\)，有 \(k\) 个质因子且最小质因子 \(\ge n^{\alpha}\) 的个数是 \(O(\frac n{\log^k n})\) 的）
查询次数：\(\sum_{\sqrt B<p\le x^{1/3}} \sqrt {\frac xp}\sim O(\frac{x^{2/3}}{\log x})\)，注意除 \(\log x\) 是因为质数分部
所以这部分的复杂度是 \(O(x^{2/3}+\frac xB+B+\frac{\sqrt {xB}}{\log B})\)
取 \(B=x^{1/3}\log^{2/3} x\)，后面可以做到 \(O((\frac{x}{\log x})^{2/3})\)，瓶颈在于树状数组的查询次数

优化：
考虑若 \(r\) 是素数，对 \(r\) 直接算前缀和，复杂度 \(O(\frac xB)\)，查询也是 \(O(1)\) 的
若 \(r\) 为非素数，由结论，此时修改是 \(O(\frac{x^{2/3}}{\log^2 x})\) 次的，且 \(r>p^2\)，而 \(p\le \frac pr\)，故 \(p\le x^{1/4}\)，询问次数为 \(O(\frac{x^{5/8}}{\log x})\)，故最后的复杂度是 \(O((\frac{x}{\log x})^{2/3})\)

Interesting Math