SPOJ : DIVCNT2 - Counting Divisors (square)

设

[f(n)=sum_{d|n}mu^2(d)]

则

[begin{eqnarray*}
sigma_0(n^2)&=&sum_{d|n}f(d)\
ans&=&sum_{i=1}^nsigma_0(i^2)\
&=&sum_{i=1}^nsum_{d|i}sum_{k|d}mu^2(k)\
&=&sum_{k=1}^nmu^2(k)G(lfloorfrac{n}{k}rfloor)
end{eqnarray*}]

其中

[G(n)=sum_{i=1}^nlfloorfrac{n}{i}rfloor]

又因为

[sum_{i=1}^nmu^2(i)=sum_{i=1}^{sqrt{n}}mu(i)lfloorfrac{n}{i^2}rfloor]

因此首先线性筛预处理出$n^{frac{2}{3}}$内的所有答案，然后分段计算即可。

时间复杂度$O(Tn^{frac{2}{3}})$。

 

#include<cstdio>
typedef long long ll;
const int N=100000010;
int T,M,tot,p[N/10],f[N];char v[N],mu[N],h[N];ll g[N],n,m,o,a[10010],old,now,ans,i,j;
inline ll F(ll n){
if(n<M)return f[n];
ll ret=0;
for(ll i=1;i<=n/i;i++)ret+=n/i/i*mu[i];
return ret;
}
inline ll G(ll n){
if(n<M)return g[n];
ll ret=0;
for(ll i=1,j;i<=n;i=j+1){
j=n/(n/i);
ret+=n/i*(j-i+1);
}
return ret;
}
void init(){
int i,j,k;
for(mu[1]=g[1]=1,i=2;i<M;i++){
if(!v[i])mu[i]=-1,g[i]=h[i]=2,p[tot++]=i;
for(j=0;j<tot&&i*p[j]<M;j++){
v[k=i*p[j]]=1;
if(i%p[j]){
mu[k]=-mu[i];
g[k]=g[i]*2;
h[k]=2;
}else{
g[k]=g[i]/h[i]*(h[i]+1);
h[k]=h[i]+1;
break;
}
}
}
for(i=1;i<M;i++)f[i]=f[i-1]+(mu[i]!=0),g[i]+=g[i-1];
}
int main(){
scanf("%d",&T);
for(o=1;o<=T;o++){
scanf("%lld",&a[o]);
if(a[o]>m)m=a[o];
}
if(m<=1000000)M=m;else{
for(M=1;1LL*M*M*M<m;M++);
M*=M;
}
init();
for(o=1;o<=T;o++){
n=a[o];
ans=old=0;
for(i=1;i<=n;i=j+1){
now=F(j=n/(n/i));
ans+=(now-old)*G(n/i);
old=now;
}
printf("%lldn",ans);
}
return 0;
}