0.更新
upd 2023.5.21 更新了关于 powerful number 数量的证明
upd 2023.5.25 更新了关于 杜教筛 的时间复杂度证明
正文
1. 筛质数
筛法其实就是判断质数的一个算法，但是是解决 \([1,n]\) 这一段区间的算法
筛质数是最简单的一个用法
1.1 暴力
最简单的方式就是对于每一个数去判断是否是质数即可，时间复杂度为 \(n^{\frac{3}{2}}\)
1.2 小筛法
其实有一个更好的想法
我们从 \(1\) 到 \(n\) 之间扫一遍，然后对于每个数，他的倍数一定是个合数，就可以判断
当然还可以优化一下，我们只用对质数这么去做就可以了，因为若一个合数 \(n=pm\)（\(p\) 为质数），则对于 \(kn\) 就可以用 \(p\times(mk)\) 就可以筛去了，没有必要再筛一遍
给出一段代码：
bool vis[maxn];//是否质数
void find_prime(int n)
{
memset(vis,1,sizeof(vis));
vis[0]=vis[1]=0;
for(int i=2;i<=n;i++)
{
if(vis[i])
{
for(int j=2*i;j<=n;j+=i)
vis[j]=0;
}
}
}
1.3 埃氏筛法
埃氏筛法其实就是在筛掉质数的倍数时进行优化
我们其实没有必要从 \(2p\) 开始枚举，可以从 \(p^2\) 开始枚举，因为之前的会被 \(1\cdots p-1\) 中的质数筛掉
这样的复杂度可以压缩到 \(O(n\log\log n)\)，常数可以说非常的小
1.4 线性筛（欧拉筛）
其实我们每一步的优化都是为了将所有数进行一定的分类进行筛除，比如之前的方式就是按有哪些质因子就分入哪些类
但是这样的话会有很多的重复
那么我们考虑怎样分类更好
我们可以以最小的质因子分类，比如 \([1,10]\) 之中，就会分为这么几类：
啥也不是：\(1\)
\(2: 2,4,6,8,10\)
\(3:3,9\)
\(5: 5\)
\(7:7\)
注意到每个数只会到一个组，那么如果我们能按照这种方式筛掉这些数就是 \(O(n)\) 的
考虑如何实现
我们考虑当前的数 \(i\) 加上哪些质因子去筛掉别人
假设最小质因子为 \(p\) 则我们只会筛 \(1\cdots p\) 中的质数
如果我们往后筛一个 \(q\)，那么设 \(i=pm\)，则 \(pqm\) 在 \(qm\) 时也会被 \(p\) 筛掉一次，不好
依此我们可以写出代码：
bool vis[maxn];//是否质数
int prime[maxn],tot;// 质数表
void find_prime(int n)
{
memset(vis,1,sizeof(vis));
vis[0]=vis[1]=0;
for(int i=2;i<=n;i++)
{
if(vis[i])
prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)
break;
}
}
}
以上就是最简单的用法，我们要开始弄一些奇奇怪怪的东西了
2.求积性函数
2.1 积性函数的定义
设 \(f(n)\) 是一个积性函数，则 \(f\) 满足
\[f(n)=f(a)f(b),(a,b)=1 \]如果 \(f(n)=f(a)f(b)\) 在 \((a,b)>1\) 时也满足，那么称为完全积性函数
最简单的积性函数有 \(I,\epsilon,id,\sigma,d,\varphi\) 等，分别的定义是这样的：
\[I(n)=1 \]\[\epsilon(n) = \left\{ \begin{array}{ll} 1 \quad n=1\\ 0 \quad otherwise \end{array} \right. \]\[id(n)=n \]\(\sigma\) 是因数和函数，计算方式是这样的：
\[\forall n=\prod\limits_{i=1}^k p_i^{\alpha_i},\sigma(n)=\prod\limits_{i=1}^{k}\sum_{j=0}^{\alpha_i} p_i^{j} \]这个东西的解释比较简单，就是讨论每个因子取多少就好了，积性证明直接展开就好了
\(d\) 是因数和函数，计算方式类似 \(\sigma\)：
\[\forall n=\prod\limits_{i=1}^k p_i^{\alpha_i},d(n)=\prod\limits_{i=1}^{k}\alpha_i+1 \]解释同上
\(\varphi(n)\) 是欧拉函数，代表 \([1,n]\) 之间与 \(n\) 互质的数的个数
他的求解方式是这样的：
\[\forall n=\prod\limits_{i=1}^k p_i^{\alpha_i},\varphi=n\times\prod\limits_{i=1}^k \frac{p_i-1}{p_i} \]感性的理解一下，比如 \(12=2\times 2\times 3\)
那么我们考虑消去 \(2\) 的倍数，只剩下 \(1,3,5,7,9,11\)
之后消去 \(3\)，剩下 \(1,5,7,11\)
注意到一个有趣的结论：\(x,n-x\) 是可以配对的，证明用最大公约数计算一下就好了
那么我们来稍微证明一下这个东西是正确的
我们先考虑证明两个质因子的情况，设 \(n=pq\)
那么容斥一下就得到 \(\varphi(n)=pq-p-q+1=(p-1)(q-1)\)
那么如果有次数的话就是将 \([1,n]\) 平移一下就好了
之后可以用归纳法去解决更多元的问题了，积性证明也是类似的
2.2 积性函数的计算
2.2.1 朴素的计算
按定义算就完了
2.2.2 线性筛
线性筛可以很好地完成这个工作，可以计算所有的积性函数并且 \(O(n)\)
我们以欧拉函数为例子解释
那么我们考虑现在的 \(i\) 和枚举到的 \(p\)
考虑 \(i\) 中是否有 \(p\)
如果有，那么根据定义 \(\varphi(ip)=p\varphi(i)\)
否则就为 \(\varphi(ip)=\varphi(i)\varphi(p-1)\)
依此转移即可
2.2.3 杜教筛
从此我们要开始一些奇奇怪怪的筛法了（都不是人能想得到的）
杜教筛呢要求解的就是 \(\displaystyle\sum_{i=1}^{n} f(i)=S(n)\)
适用场景：能找到函数 \(g,h\)，\(f*g=h\) 且能快速求出 \(g,h\) 的前缀和
那么我们考虑 狄利克雷卷积
\[\sum_{i=1}^n (f * g)(i) \]\[=\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{i}{d}) \]\[=\sum_{i=1}^n g(i)\sum_{j=1}^{\frac{n}{d}} f(j) \]\[=\sum_{i=1}^n g(i)S(\frac{n}{d}) \]如果我们能适当选取简单的 \(g\) 和 \((f*g)\)，那么我们就可以直接求出 \(\sum_{i=1}^n g(i)S(\frac{n}{d})\) 和 \(\sum_{i=2}^n g(i)S(\frac{n}{d})\)
然后就可以求出 \(g(1)S(n)\)
前者十分容易求出，考虑后者
后者我们可以采取整除分块的方式，根号求解，但我们需要求出 \(S(\frac{n}{d})\)，可以递归求解
直接使用好像是 \(O(n^{\frac{3}{4}})\) 的？
一般来说，我们会预先线性处理 \(10^6\) 内的数的前缀和，之后可以降到 \(O(n^{\frac{2}{3}})\)
接下来给出直接使用的复杂度证明：
注：其中放缩部分等号并不一定相等，微小误差不计，但都一定保证是向大放缩
注意到一件事情：\([\frac{[\frac{n}{a}]}{b}]\) = \([\frac{n}{ab}]\)
所以我们可以只用关注所有 \([\frac{n}{x}]\) 的位置的时间复杂度
注意到我们每次其实只会对于每个点计算一次，所以所有的地方只统计一次要注意
在每一个 \(x\) 我们会消耗 \(\sqrt x\) 时间进行计算
那么柿子就是 \(\displaystyle\sum_{i=[\frac{n}{x}]} \sqrt{i}\)
对于 \(i\le \sqrt n\) 时，柿子可以放缩为 \(O(n^{\frac{3}{4}})\)
而对于后面的，可以计算为 \(\displaystyle\sum_{i=1}^{\sqrt n}\sqrt{\frac{n}{i}}\)
变换一下，可以变为 \(\displaystyle\sqrt n\sum_{i=1}^{\sqrt n} \sqrt{\frac{1}{i}}=O(n^{\frac{3}{4}})\)
2.2.4 powerful number 筛
这也是一个奇奇怪怪的筛法，也是解决积性函数前缀和的东西，可以简称 PN 筛
适用场景：
存在一个函数 \(g\) 使得：
-
\(g\) 是积性函数
-
\(g\) 易求前缀和
-
对于 \(p\text{ is a prime}\)，有 \(g(p)=f(p)\)
首先我们先来定义什么是 powerful number
如果一个数 \(n=\prod\limits_{i=1}^k p_i^{\alpha_i}\)，满足 \(\forall i\le k,\alpha_i>2\)，则 \(n\) 就是一个 powerful number
注意到两个个事实：
1.所有的 powerful number 都可以表示为 \(a^2b^3\)
证明：考虑一个数 \(n\) 的素因子 \(p\)，\(p^{\alpha}||n\)
那么因为 \(n\) 是一个 powerful number，所以 \(\alpha >1\)
同时我们考虑 \(a,b\) 中 \(p\) 的质因子个数，设为 \(x,y\)
那么就有 \(2x+3y=\alpha\)，考虑这个方程是否有解
引入一个结论：
如果方程 \(ax+by=N\) 中，\(N>ab-a-b\)，则方程必定有解
这个结论相对来说容易证明
那么只要 \(\alpha>2\times 3-2-3=1\) 就可以说明方程必定有解，这件事情已经知道，证明完毕
2.\([1.n]\) 中 powerful number 的数量是 \(O(\sqrt n)\) 的，这也是 powerful number 筛法的一个重要基础
证明：
注：以下证明中每步等号略有误差，但忽略不计
我们考虑先去找 \(a\) 之后再去算有多少个 \(b\) 满足
那么就为 \(\displaystyle\sum_{i=1}^{\sqrt{n}}[\sqrt[3]{\frac{n}{i^2}}]\)
\[=\displaystyle\sum_{i=1}^{\sqrt{n}}\sqrt[3]{\frac{n}{i^2}} \]\[=n^{\frac{1}{3}}\sum_{i=1}^{\sqrt{n}}\sqrt[3]{\frac{1}{i^2}} \]\[=n^{\frac{1}{3}}\sqrt{\sum_{i=1}^{\sqrt{n}}\sqrt[3]{\frac{1}{i}}} \]\[=n^{\frac{1}{3}}\sqrt{\sum_{i=1}^{\sqrt{n}}{\frac{1}{\sqrt[3]{i}}}} \]\[=n^{\frac{1}{3}}\sqrt{\sum_{d=1}^{\sqrt[6]{n}+1}\frac{(d+1)^3-d^3}{d}} \]\[=n^{\frac{1}{3}}\sqrt{\sum_{d=1}^{\sqrt[6]{n}+1}\frac{3d^2+3d+1}{d}} \]\[=n^{\frac{1}{3}}\sqrt{\sum_{d=1}^{\sqrt[6]{n}+1}O(d)} \]\[=n^{\frac{1}{3}}\times O(n^{\frac{1}{6}}) \]\[=O(n^{\frac{1}{2}}) \]证毕
同样，PN 筛也是去构造一个特殊的积性函数 \(g\)，使得 \(\forall p\text{ is a prime},g(p)=f(p)\)，同时记一个函数 \(h\)，使得 \(g*h=f\)，同样也是积性的
给出一个 例题
那么在这里， \(g(p)=p(p-1)\)，我们可以设这个函数为 \(g(n)=n\varphi(n)\)，这是满足 \(g(p)=f(p)\) 的
注意到对于 \(p\)，有 \(f(p)=g(p)h(1)+g(1)h(p)=f(p)+h(p)\)
所以有 \(h(p)=0\)，\(h\) 只有在所有 powerful number 处可能不为 0
那么考虑怎样计算 \(h(n)\)，我们不妨先讨论对于 \(h(p^k)\) 如何计算
我们知道 \(f(p^k)=\displaystyle\sum_{i=0}^kg(p^i)h(p^{k-i})\)
那么就有 \(h(p^k)=f(p^k)-\displaystyle\sum_{i=1}^k g(p^i)h(p^{k-i})\)
我们可以直接暴力计算出所有的 \(h\) 在 \(p^k\) 处的值，接着直接搜索 powerful number（因为个数是 \(O(\sqrt n)\) 的），然后拟合就可以了
我们求出了 \(g,h\) 就可以开始后面的推导了
我们要求的答案就是 \(\displaystyle\sum_{i=1}^{n}(g*h)\)
\[\displaystyle\sum_{i=1}^{n}(g*h) \]\[=\sum_{i=1}^n\sum_{d|n}g(d)h(\frac{n}{d}) \]\[=\sum_{i=1}^nh(i)\sum_{d=1}^{[\frac{n}{d}]}g(d) \]注意到求和的后半段是一个前缀和的形式，我们可以直接采用杜教筛求出
总的时间复杂度瓶颈在杜教筛的 \(O(n^{\frac{2}{3}})\)
那么现在又有一个新问题：\(g(n)=n\varphi(n)\) 这个函数咱们不会用杜教筛算啊怎么办
其实也是可以算的，在 \(g'(n)=\varphi(n)\) 时，我们选取的函数为 \(I\)，那么根据狄利克雷卷积的性质：\((h(n)\cdot id)*(g(n)\cdot id)=f(n)\cdot id\)，其中 \((h*g)=f\)，在这里就会有 \((id\cdot \varphi)*id=id^2\)，可以用杜教筛求
2.2.5 min25 筛
min25 筛与前两种筛法想法不太相同，min25 筛的起点是埃氏筛法，它可以做到 \(O(\frac{n^{\frac{3}{4}}}{log n})\) 求出积性函数前缀和
适用场景：\(f(p)\) 要是一个关于 \(p\) 项数较少的多项式或可以快速求值；\(f(p^c)\) 可以快速求值
一些记号：
\(p_k\) 代表第 \(k\) 小的质数
\(lpf_i\) 代表 \(i\) 的最小质因子
接下来我们开始讲解算法
min25 筛想法就是我们将质数和合数还有 1 的求值分开计算
首先 \(f(1)=1\) 是显然的
首先我们要先求质数的，也就是 \(\displaystyle\sum_{i=1}^{n}[p\text{ is a prime}]f(p)\)
我们考虑记 \(F(n,k)\) 代表 \(\displaystyle\sum_{i=2}^n[p_k< lpf_i \ or\ i\text{ is a prime}]g(i)\)，这里 \(g(i)=i^k\)，因为 \(f\) 是一个多项式，我们可以求出不同次数的然后进行拟合
那么我们要求的就是 \(F(n,\infty)\)
我们考虑在 \(F(n,k)\) 和 \(F(n,k-1)\) 之间建立联系
注意到 \(F(n,k)\) 相对于 \(F(n,k-1)\) 应该限制是更大了，所以应该是删掉了一些东西
我们考虑一件事 \(p_k^2\le n\) 是否成立
如果 \(p_k^2>n\)，从埃氏筛法考虑，那么就意味着不会筛掉新的数，所以 \(F(n,k)=F(n,k-1)\)
否则就有可能会筛掉一些数
有转移式 \(F(n,k)=F(n,k-1)-g(p_k)(F(\frac{n}{p_k},k-1)-F(p_{k-1},k-1))\)
解释一下，首先我们先把 \(F(n,k-1)\) 直接继承过来再减去 \(lpf_i=p_k\) 的情况
注意到一个非常重要的事情：\(g\) 是一个完全积性函数
这就意味着我们不需要一次提出所有的 \(p_k\) 也可以保证正确性了
然后我们就可以直接用 \(F(\frac{n}{p_k},k-1)\) 了
但是为什么还要减去最后的呢？注意到我们这个 \(F(\frac{n}{p_k},k-1)\) 中还残留了一些小于 \(p_k\) 的质数，如果相乘得到的 \(x=p_kp_t\) 的 \(lpf_x\) 就会为 \(p_t\) 而不是 \(p_k\)，所以要减去前面的质数
最后我们用不同的 \(g\) 拟合出 \(f\) 即可
第二部分，我们要开始加上合数的贡献了
我们记 \(S(n,k)\) 代表 \(\displaystyle\sum_{i=2}^n[lpf_i>p_k]f(i)\)
那么我们所要的答案就是 \(S(n,0)+1\)
考虑我们现在要求 \(S(n,k)\)
同样进行拆分：\(i\) 为质数和不为质数
首先对于 \(i\) 为质数的部分，我们直接用 \(F(n,\infty)-F(p_k,k)\) 就可以算出来
然后考虑为合数的部分
我们可以直接枚举下一个质因子 \(p_x\)以及他的次数，然后将 \(p_x^e\) 直接提出来进行计算，就有：
\[\sum_{p_x^e\le n,k<x}f(p_x^e)(S(\frac{n}{p_k^e},x)+[e\not=1]) \]解释一下为什么有一个 \([e\not=1]\)，因为如果 \(e\) 等于 \(1\) 的话就会有一个 \(f(p_x)\) 这个已经在质数的时候算过了
以上就是算法流程，接下来我们讲一点实现的东西
首先我们注意到其实 \(S,F\) 的第一维是有可能到达 \(n\) 的级别的，但是我们的 \(n\) 很大，怎么办呢？
首先对于 \(F\)
我们注意到一件事情：\(\lfloor\frac{\frac{n}{a}}{b}\rfloor=\lfloor\frac{n}{ab}\rfloor\)
而 \(\lfloor\frac{n}{x}\rfloor\) 只有 \(O(\sqrt n)\) 种选择，可以压缩
而第二维可以滚掉，总的空间就不会爆炸
而对于 \(S\)，根据一堆大佬的证明，不需要记忆化也可以保证复杂度
总的空间就被我们压到了 \(O(\sqrt n)\)
时间复杂度之后填上
3.总结
一下给出普通筛质数的筛法和积性函数的筛法之间的对比
筛出质数：
| 类别 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力判断质数 | \(O(n^{\frac{3}{2}})\) | \(O(n)\) |
| 小筛法 | 约为\(O(n\log\log n)\) | \(O(n)\) |
| 埃氏筛法 | \(O(n\log\log n)\) | \(O(n)\) |
| 欧拉筛 | \(O(n)\) | \(O(n)\) |
求积性函数（简单的积性函数）：
| 类别 | 时间复杂度 | 空间复杂度 | 限制 |
|---|---|---|---|
| 欧拉筛 | \(O(n)\) | \(O(n)\) | 无 |
| 杜教筛 | \(O(n^{\frac{2}{3}})\) | \(O(\sqrt n)\) | 必须找到好算的 \(g,h,h=f*g\) |
| powerful number 筛 | \(O(n^{\frac{2}{3}}\)) | \(O(\sqrt{n})\) | 必须找到好算的 \(g,g(p)=f(p)\) |
| min25筛 | \(O(\frac{n^\frac{3}{4}}{\log n})\) | \sqrt | \(f(p)\) 好计算或者是较简单的多项式 |