杜教筛谁发明的，bzoj3944 Sum 杜教筛

模板题，注意杜教筛化式子的技巧：

1、构造求和函数

2、利用积性函数约数性质

3、做差算出单项

杜教筛谁发明的、4、约数倍数转化贡献

5、分块求商

码：

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
using namespace std;
#define M 3000000
#define ll long long 
int tot,i,j,T,su[M+5];
ll ans,phe[M+5],n[999],N,mhe[M+5],mu[M+5],phi[M+5];
bool he[M+5];
map<int,ll>pma;
map<int,int>mma;
void eular()
{mu[1]=phi[1]=1;for(i=2;i<=N;i++){if(!he[i]){su[++tot]=i;			phi[i]=i-1;mu[i]=-1;}for(j=1;j<=tot&&su[j]*i<=N;j++){int k=su[j]*i;he[k]=1;if(i%su[j]==0){phi[k]=su[j]*phi[i];mu[k]=0;break;}else{phi[k]=phi[i]*phi[su[j]];mu[k]=-mu[i];}	}}for(i=1;i<=N;i++)phe[i]=phe[i-1]+phi[i],mhe[i]=mhe[i-1]+mu[i];	
}
ll dfs1(ll o)
{if(o<=N)return phe[o]; if(pma[o])return pma[o];
ll lin=o*(1+o)/2;
ll l;
for(l=2;l<=o;l++)
{
ll oo=o/l;
lin-=((o/oo)-l+1)*dfs1(oo) ;
l=o/oo;	
}	
pma[o]=lin;
return lin;
}
int dfs2(int o)
{	if(o<=N)return mhe[o]; if(mma[o])return mma[o];
int lin=1;
unsigned int l;
for(l=2;l<=o;l++)
{
int oo=o/l;
lin-=((o/oo)-l+1)*dfs2(oo);
l=o/oo;	
}
mma[o]=lin;
return lin;
}
int main()
{scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%lld",&n[i]);
N=max(n[i],N);	
}
N=pow(N,2.000/3) ;
eular();
for(i=1;i<=T;i++)
{
printf("%lld ",dfs1(n[i]));
printf("%d\n",dfs2(n[i]));	
}
}