设
\[f(n)=\sum_{d|n}\mu^2(d)\]
则
\[\begin{eqnarray*}
\sigma_0(n^2)&=&\sum_{d|n}f(d)\\
ans&=&\sum_{i=1}^n\sigma_0(i^2)\\
&=&\sum_{i=1}^n\sum_{d|i}\sum_{k|d}\mu^2(k)\\
&=&\sum_{k=1}^n\mu^2(k)G(\lfloor\frac{n}{k}\rfloor)
\end{eqnarray*}\]
其中
\[G(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]
又因为
\[\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{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("%lld\n",ans);
}
return 0;
}