I 前言&引入

在此文章中，我们假设您已经彻底理解欧拉筛的原理，明白积性函数的定义，会使用欧拉筛计算欧拉函数等基础应用。

让我们先看一道例题：

例题

定义集合

\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)

。

1\le Q,x\le 10^7

。

（不考虑读入读出）

首先，先跑一遍欧拉筛，把

\operatorname{rk}(x)

预处理出来。

我们发现，在预处理

\operatorname{f}(x)

时，若使用欧拉筛，那么在欧拉筛板子对应高亮部分难以处理。

CPP

123456789101112131415for(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 关于代码

先放代码再说，此处使用线性筛模版题。

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）地想出来的，可能已经有前人发明。如果有，请私信我，我会在文中补充。

谢谢阅读喵。

浅谈一种更方便的的线性解积性函数方式

文章操作