各种筛子
donotctjuntilAFO
·
2023-08-23 08:04:54
·
算法·理论
前言
oi中有一堆筛子，如：埃氏筛、线性筛、杜教筛、powerfulnumber筛、冷群筛、洲阁筛、min25筛、lwx爷爷筛。
正文
埃氏筛
通常用来筛质数，每次用质数的倍数来标记合数，复杂度 O(n\log \log n)。
f(i,2,n)
if(!vis[i])
for(int j=i<<1;j<=n;j+=i)
vis[j]=1;
优化：
我们每次只要筛到 \sqrt n 就足够了。
我们可以只筛奇数。
用 bitset 优化。
代码：
bitset
void init(int n){
for(int j=4;j<=n;j+=2)
vis[j]=1;
for(int i=3;i*i<=n;i+=2)
if(!vis[i])
for(int j=i*i;j<=n;j+=i)
vis[j]=1;
}
此时效率已经比一般的线性筛都要快了。
应用：记录 1\sim n 中的所有数的质因数。
在筛的同时记录即可。
代码：
f(i,2,n)
if(!vis[i]){
prime[i][++cnt[i]]=i;
for(int j=i<<1;j<=n;j+=i)
vis[j]=1,prime[j][++cnt[j]]=i;
}
线性筛
只用每个数的最小质因子标记，这样就只会标记一次，复杂度 O(n)。
代码：
f(i,2,n){
if(!vis[i])
prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
vis[i*prime[j]]=1;
if(!(i%prime[j]))
break;
}
}
应用：如果一个积性函数 f 可以 O(1) 计算 f(p^k) 就可以在 O(n) 内求出函数 1\sim n 的值，如 \varphi,\mu,d,\sigma 。
杜教筛
可以快速算出大部分积性函数（甚至普通函数）的前缀和。
我们要算， S(n)=\displaystyle \sum_{i=1}^{n}f(i)
只要我们找到一个积性函数 g 使得可以快速算出 \displaystyle \sum_{i=1}^{n}(f\ast g)(i) 和 g(i) 。
那么 \displaystyle S(n)=\frac{\sum_{i=1}^{n}(f\ast g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)}{g(1)}
用数论分块求 \displaystyle \sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor) 即可，复杂度 O(n^{\frac{3}{4}}) 。
如果能用线性筛预处理出 S(1)\sim S(k) 取 k=n^{\frac{2}{3}} 得最优复杂度 O(n^{\frac{2}{3}}) 。
例1 求 \displaystyle \sum_{i=1}^{n}\varphi(i),\sum_{i=1}^{n}\mu(i)
易得 \varphi\ast 1=\mathrm{id},\mu\ast 1=\epsilon .
代码：
#include
#define f(i,l,r) for(int i=l;i<=r;++i)
#define F(i,r,l) for(int i=r;i>=l;--i)
#define int long long
#define ULL unsigned long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define read(n) {int _x=0,_ty=1;char _c=getchar();while(!isdigit(_c)){if(_c=='-')_ty=-1;_c=getchar();}while(isdigit(_c))_x=10*_x+_c-'0',_c=getchar();n=_x*_ty;}
char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
const int N=3000005;
int T,n,prime[N],cnt,mu[N],phi[N];
bool vis[N];
map
void init(int n){
mu[1]=phi[1]=1;
f(i,2,n){
if(!vis[i])
prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
vis[i*prime[j]]=1;
if(i%prime[j])
mu[i*prime[j]]=-mu[i],phi[i*prime[j]]=phi[i]*(prime[j]-1);
else{
phi[i*prime[j]]=phi[i]*prime[j];break;
}
}
}
f(i,1,n)
phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
int sumphi(int n){
if(n<=3000000)
return phi[n];
if(sphi[n])
return sphi[n];
int ans=(n+1)*n>>1;
for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans-=(r-l+1)*sumphi(n/l);
}
return sphi[n]=ans;
}
int summu(int n){
if(n<=3000000)
return mu[n];
if(smu[n])
return smu[n];
int ans=1;
for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans-=(r-l+1)*summu(n/l);
}
return smu[n]=ans;
}
signed main(){
read(T);
init(3000000);
while(T--){
read(n);
printf("%lld %lld\n",sumphi(n),summu(n));
}
return 0;
}