杜教筛起源于中学信息学队员杜瑜皓
它结合了三种算法,分别是:整除分块,狄利克雷卷积和线性筛
它主要是求解n较大时的积性函数的值
它的时间复杂度是O(n^(2/3)),小于O(n)
杜教筛在竞赛中很难出现
这是一道模板题,给出代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 5e6+39+7; int prime[N],mu[N];ll phi[N];bool vis[N]; unordered_map<int,int>summu; unordered_map<int,ll>sumphi; void init(){ int cnt=0; vis[0]=vis[1]=1; mu[1]=phi[1]=1; for(int i=2;i<N;i++){ if(!vis[i]){ prime[cnt++]=i; mu[i]=-1; phi[i]=i-1; } for(int j=0;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]*phi[prime[j]]; }else{ mu[i*prime[j]]=0; phi[i*prime[j]]=phi[i]*prime[j]; break; } } } for(int i=1;i<N;i++){ mu[i]+=mu[i-1]; phi[i]+=phi[i-1]; } } int gsum(int x){return x;} ll getsmu(int x){ if(x<N)return mu[x]; if(summu[x])return summu[x]; ll ans=1; for(ll l=2,r;l<=x;l=r+1){ r=x/(x/l); ans-=(gsum(r)-gsum(l-1))*getsmu(x/l); } return summu[x]=ans/gsum(1); } ll getsphi(int x){ if(x<N)return phi[x]; if(sumphi[x])return sumphi[x]; ll ans=x*((ll)x+1)/2; for(ll l=2,r;l<=x;l=r+1){ r=x/(x/l); ans-=(gsum(r)-gsum(l-1))*getsphi(x/l); } return sumphi[x]=ans/gsum(1); } int main(){ init();int T;cin>>T; while(T--){ int n;cin>>n; cout<<getsphi(n)<<' '<<getsmu(n)<<'\n'; } return 0; }
标签:int,ll,long,杜教,vis,unordered From: https://www.cnblogs.com/zhanghx-blogs/p/17538679.html