浅谈一种更方便的的线性解积性函数方式
watermouthhang
·
·
算法·理论
I 前言&引入
在此文章中，我们假设您已经彻底理解欧拉筛的原理，明白积性函数的定义，会使用欧拉筛计算欧拉函数等基础应用。
让我们先看一道例题：
::::info[例题]
定义集合 \mathbb{P} 为质数集。
定义函数 \operatorname{rk}(x),x\in \mathbb{P} 表示 x 是第 \operatorname{rk}(x) 个质数，如 \operatorname{rk}(2)=1,\operatorname{rk}(3)=2,\operatorname{rk}(5)=3。
定义积性函数 \operatorname{f}(x) 在 p^k,p\in \mathbb{P},n\in \mathbb{N} 处取值为 k\cdot \operatorname{rk}(p)+1。
共 Q 次询问，每次询问一个 \operatorname{f}(x)。
（不考虑读入读出）
::::
首先，先跑一遍欧拉筛，把 $\operatorname{rk}(x)$ 预处理出来。
我们发现，在预处理 $\operatorname{f}(x)$ 时，若使用欧拉筛，那么在欧拉筛板子对应高亮部分难以处理。
```cpp line-numbers lines=10-13
for(int i=2;i<=n;++i)
{
if(!is_np[i])
{
Prime[++cnt]=i;
}
for(int j=1;1ll*ps[j]*i<=n;++j)
{
is_np[ps[j]*i]=1;
if(i%ps[j]==0)
{
break;
}
}
}
```
当然，使用欧拉筛肯定是可行的，只要开一个记录被筛的最小质因子，和最小质因子的次数，将其除去倒找也可，但是对于状态复杂的积性函数求解问题而言，终究思路略显繁杂。
于是，本文的主角——**明灯筛（Sieve of Tomo in Row，RR）法**就krkrdkdk的登场了。
# II 明灯筛
我们先来回顾一下欧拉筛。
欧拉筛的本质是什么？**让每个数的最小质因子把它筛去**。这样每个数只会被筛一次，时间复杂度达到 $\operatorname{O}(n)$。
但是，欧拉筛并不完全适配积性函数的求解问题。当数字的最小质因子不止为一次时，就要重新设定转移方程，乃至通过上文的方法“溯源”，在思维量上略大。
有没有不耗脑子的方法呢？我们稍稍改变策略，**让一个数的所有最小质因子之积把它筛去**。什么意思呢？如果我们将正在被筛的数 $n$ 质因数分解为 $p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n},p_1<p_2<\cdots<p_n$，那么将它筛去的就是 $p_1^{k_1}$。
容易发现，每个数只会被 $p_1^{k_1}$ 这一个数筛去，因此这样做的时间复杂度为 $\operatorname{O}(n)$。
对于这种筛法，我们惊讶地发现，使用它求解积性函数时，只需要处理好所有质数的整次幂，就可以在转移过程中**直接相乘**了！这样，我们就可以使用较少的思维量解决问题了。
# III 关于代码
先放代码再说，此处使用[线性筛模版题](https://www.luogu.com.cn/problem/P3383)。
```cpp
#include <cstdio>
#include <bitset>
using namespace std;
typedef long long ll;
constexpr int maxn=1e8+10;
bitset<maxn> bs;
int Prime[(int)(2e7+10)];
int cnt,n,q;
ll i,j,cg,k;
int main()
{
bs[0]=bs[1]=1;
cnt=0;
scanf("%d %d",&n,&q);
for(i=2;i<=n;++i)
{
if(!bs[i])
{
Prime[++cnt]=i;
for(k=i*i;k<=n;k*=i)
{
bs[k]=1;
}
}
for(j=1;j<=cnt&&i%Prime[j]!=0;++j)
{
cg=Prime[j];
while(cg*i<=n)
{
bs[cg*i]=1;
cg*=Prime[j];
}
if(cg==Prime[j])
{
break;
}
}
}
while(q--)
{
scanf("%lld",&k);
printf("%d\n",Prime[k]);
}
return 0;
}
```
注意：在处理次幂时，不可以每次单独计算，应当在递推过程中逐步计算，否则时间复杂度会不正确。
# IV 后记
本文使用 $20$ 分钟写完，可能有误，可以在评论指出。
**明灯筛**是我在上一节无聊的物理课（就那一节无聊，平常都很有意思的）时**偷摸（tomo）地**想出来的，可能已经有前人发明。如果有，请私信我，我会在文中补充。
谢谢阅读喵。