三道相似的筛法题

时间:2024-10-04 07:22:52

有如下三题:

P1835 素数密度
Prime Distance
P3601 签到题

细心观察,发现这几道题都考察了筛法相关知识,但数据范围巨大,即便是线性筛、杜教筛也无法解决。但给定的区间长度却可以接受,所以就出现了比较巧的做法。

P1835 素数密度:

[ l , r ] [l,r] [l,r] 中质数的个数。

可以先筛出 r \sqrt{r} r 中的所有质数,然后用这些质数来筛 [ l , r ] [l,r] [l,r] 中的质数,过程类似埃氏筛法。设 x x x 为区间长度,则时间复杂度 O ( r l n r x l o g l o g x ) O(\frac{\sqrt{r}}{ln\sqrt{r}}xloglogx) O(lnr r xloglogx),能够通过此题。

Prime Distance:

与上一题非常类似,依然是筛出所有质数,然后去更新最大、最小值就行了,不过多赘述。

P3601 签到题:

观察到 q i a n d a o ( x ) qiandao(x) qiandao(x) 实际就是 x − ϕ ( x ) x-\phi{(x)} xϕ(x),所有求出 [ l , r ] [l,r] [l,r] 中的所有欧拉函数值就可以解决此题。但数据范围依然很大,区间长度很小,所以继续考虑上述做法。

可以先把 r \sqrt{r} r 中的所有质数筛出,然后用它们计算 [ l , r ] [l,r] [l,r] 中的欧拉函数值,利用欧拉函数的求解公式,在质因数分解过程中求。最后再特判一下大于 r \sqrt{r} r 的质数即可。

这道题贴一下代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,mod=666623333;

int l,r,prime[N],vis[N],cnt,phi[N],val[N],ans;

void init(int n){//线性筛
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;prime[j]*i<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin>>l>>r;init(sqrt(r));
	for(int i=l;i<=r;i++) phi[i-l]=val[i-l]=i;
	for(int i=1;i<=cnt;i++){
		for(int j=((l-1)/prime[i]+1)*prime[i];j<=r;j+=prime[i]){
			if(val[j-l]%prime[i]==0){
				phi[j-l]=phi[j-l]/prime[i]*(prime[i]-1);
				while(val[j-l]%prime[i]==0) val[j-l]/=prime[i];
			}
		}
	}
	for(int i=l;i<=r;i++) if(val[i-l]!=1) phi[i-l]=phi[i-l]/val[i-l]*(val[i-l]-1);
	for(int i=l;i<=r;i++) (ans+=i-phi[i-l])%=mod;
	cout<<ans<<endl;
	
	return 0;
}