\[\begin{eqnarray*}
ans&=&\sum_{i=1}^ng(i)\\
&=&\sum_{i=1}^n\sum_{d|i}\mu^2(d)\\
&=&\sum_{i=1}^n\sum_{d|i}\sum_{k^2|d}\mu(k)\\
&=&\sum_{k=1}^n\mu(k)\sum_{k^2|d}\lfloor\frac{n}{d}\rfloor\\
&=&\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k^2}\rfloor}\lfloor\frac{n}{k^2i}\rfloor\\
&=&\sum_{k=1}^{\sqrt{n}}\mu(k)S(\lfloor\frac{n}{k^2}\rfloor)
\end{eqnarray*}\]

其中

\[S(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]

枚举所有$k$，然后分段计算$S$即可，当$n$比较小的时候可以记忆化$S(n)$。

时间复杂度

\[\begin{eqnarray*}
T(n)&=&O(\sqrt{n}+\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i^2}})\\
&=&O(\sqrt{n}\sum_{i=1}^{\sqrt{n}}\frac{1}{i})\\
&=&O(\sqrt{n}\log n)
\end{eqnarray*}\]

#include<cstdio>typedef long long ll;const int N=1000010,P=1000000007;int T,C,tot,p[N/10],i,j,ans,f[N];char mu[N],v[N];ll n;inline int F(ll n){  if(n<N)if(f[n])return f[n];  ll t=0;  for(ll i=1,j;i<=n;i=j+1)j=n/(n/i),t+=n/i*(j-i+1);  t%=P;  if(n<N)f[n]=t;  return t;}int main(){  for(mu[1]=1,i=2;i<N;i++){    if(!v[i])mu[i]=-1,p[tot++]=i;    for(j=0;j<tot&&i*p[j]<N;j++){      v[i*p[j]]=1;      if(i%p[j])mu[i*p[j]]=-mu[i];else break;    }  }  for(scanf("%d",&T);T--;printf("Case #%d: %d\n",++C,(ans+P)%P)){    scanf("%I64d",&n);    for(ans=0,i=1;i<=n/i;i++)if(mu[i])ans=(ans+F(n/i/i)*mu[i])%P;  }  return 0;}

HDU5942 : Just a Math Problem