首页 > 代码库 > SPOJ : DIVCNT2 - Counting Divisors (square)
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}^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;}
SPOJ : DIVCNT2 - Counting Divisors (square)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。