题解 P4213 【【模板】杜教筛（Sum）】
shadowice1984
2018-12-06 13:03:52
大家好我非常喜欢硬核筛法于是我用一个复杂度是$O(n^{1-\epsilon})$的算法过了这题
嗯没错它就是传说中的**min_25筛**
如果您不是很了解什么是min_25筛以及这个算法能干什么的话可以去看[这篇博客](https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-sp34096)学习一下
那么我们现在来看发现这就是一道min_25筛的板子题
对于$\phi$函数来讲我们发现$f(p)=p-1,f(p^c)=(p-1)p^{c-1}$
那么关于$\phi$函数在质数的点值和可以通过处理质数和有几个质数然后两个减一下来完成
然后我们发现接下来套个min_25筛板子就可以筛$\phi$了
对于$\mu$函数来讲我们发现$f(p^c)=(-1)[c==1]$那么$\mu$在质数的点值和可以处理有几个质数然后取个相反数来完成
接下来套min_25筛板子筛的时候需要注意一下由于$f(p^c)(c>1)$是0因此我们无需枚举指数(因为都是0)
然后这题就做完了，也没必要卡什么常数，写写就过去了~
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;const int N=5*1e4+10;typedef long long ll;
int zhi[N];bool book[N];int ct;ll n;ll pres[N];
ll premu[N];ll prephi[N];ll dp1[N];ll dp2[N];ll cnt1[N];ll cnt2[N];
ll q[N];int hd;int lim;
inline ll solvephi(ll p,int q)//大力筛phi
{
if(p<zhi[q])return 0;
ll ret=((p<=lim)?dp1[p]:dp2[n/p])-prephi[q-1];
if(q==ct+1)return (p<=(ll)zhi[ct])?0:ret;int t;ll pw;ll nph;
for(int k=q;k<=ct&&(ll)zhi[k]*zhi[k]<=p;k++)
for(t=1,pw=zhi[k],nph=pw-1;pw<=p;pw*=zhi[k],nph*=zhi[k],t++)
ret+=nph*(solvephi(p/pw,k+1)+(t>1));return ret;
}
inline ll solvemu(ll p,int q)//大力筛mu
{
if(p<zhi[q])return 0;
ll ret=((p<=lim)?cnt1[p]:cnt2[n/p])-premu[q-1];
if(q==ct+1)return (p<=(ll)zhi[ct])?0:ret;
for(int k=q;k<=ct&&(ll)zhi[k]*zhi[k]<=p;k++)ret-=solvemu(p/zhi[k],k+1);
return ret;
}
inline void calc1()//求有几个质数
{
for(int i=1;i<=lim;i++)cnt1[i]=i-1;for(int i=1;i<=hd;i++)cnt2[i]=q[i]-1;
for(int j=1,t1=hd;j<=ct;j++)
{
ll lt=zhi[j]*zhi[j];while(lt>q[t1]&&t1>=1)t1--;
for(int i=1;i<=t1;i++)
{ll fv=q[i]/zhi[j];fv=(fv<=lim)?cnt1[fv]:cnt2[n/fv];cnt2[i]-=fv-j+1;}
for(int i=lim;i>=lt;i--)cnt1[i]-=cnt1[i/zhi[j]]-j+1;
}for(int i=1;i<=lim;i++)cnt1[i]=-cnt1[i];for(int i=1;i<=hd;i++)cnt2[i]=-cnt2[i];
}
inline void calc2()//求所有质数的和
{
for(int i=1;i<=lim;i++)dp1[i]=(ll)i*(i+1)/2-1;for(int i=1;i<=hd;i++)dp2[i]=q[i]*(q[i]+1)/2-1;
for(int j=1,t1=hd;j<=ct;j++)
{
ll lt=zhi[j]*zhi[j];while(lt>q[t1]&&t1>=1)t1--;
for(int i=1;i<=t1;i++)
{
ll fv=q[i]/zhi[j];fv=(fv<=lim)?dp1[fv]:dp2[n/fv];
dp2[i]-=(ll)zhi[j]*(fv-pres[j-1]);
}
for(int i=lim;i>=lt;i--)dp1[i]-=(ll)zhi[j]*(dp1[i/zhi[j]]-pres[j-1]);
}for(int i=1;i<=lim;i++)dp1[i]+=cnt1[i];for(int i=1;i<=hd;i++)dp2[i]+=cnt2[i];
}
inline void solve()
{
scanf("%lld",&n);lim=sqrt(n);for(ct=1;zhi[ct]<=lim;ct++);ct--;hd=0;
for(ll i=1,r;i<=n;i=r+1){r=n/i;if(r>lim)q[++hd]=r,r=n/r;else break;}
calc1();calc2();printf("%lld %lld\n",solvephi(n,1)+1,solvemu(n,1)+1);
}
int main()
{
for(int i=2;i<=N-10;i++)
{
if(book[i]==false){zhi[++ct]=i;}
for(int j=1;j<=ct&&i*zhi[j]<=N-10;j++)book[i*zhi[j]]=true;
}for(int i=1;i<=ct;i++)pres[i]=pres[i-1]+zhi[i];
for(int i=1;i<=ct;i++)premu[i]=-i;
for(int i=1;i<=ct;i++)prephi[i]=pres[i]-i;int T;
scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;//拜拜程序~
}
```