SPOJ DIVCNT2
题目大意:
求\(S2(n)=\sum_{i=1}^{n}\sigma_0{(i^2)}\) 。
题解
我们可以先考虑括号里只有一个\(i\)的情况,这样,我们把\(i\)分解质因数为$p_1^{a_1}*p_2^{a_2}...p_k^{a_k} $。
那么这就是一个经典的问题,答案为
\[ \sum_{i-1}^n \prod_{j=1}^{k}(a_j+1) \] 现在\(i\)变成了\(i^2\)那么无非就是每个质因子的指数乘以2,所以答案就是:\[ \sum_{i-1}^n \prod_{j=1}^{k}(2a_j+1) \] 这是一堆二项式乘起来的形式,每一个质因子可以选或不选,考虑每一种方案是往\(2a_j\)去还是往1那边去,我们可以枚举一个往\(2a_j\)去的质因子集合,那么这时候的方案数就是\(\prod_{j}2a_j\)。如果我们把里面的那个2提出来的话,那么这就是一个枚举所有的\(>0\)的\(a_j\)也就是枚举约数的过程,考虑对于每个约数,因为刚才我们把2提出来了,它的前面还乘上了\(2^{集合大小}\),这里的集合大小就是这个数的质因子个数,所以我们最后的答案就是:
\[ \sum_{i=1}^{n}\sum_{d|n}2^{w(d)} \] 如果我们把\(w(d)\)看做每个质因数选或者不选,那么这个就是\(d\)的无平方因子的约数个数,考虑\(\mu\)函数的平方,如果这个数有平方因子那么就为0,否则就为1,所以答案变成:\[ \sum_{i=1}^n\sum_{d|n}\sum_{x|d}\mu^2(x) \] 然后我们把枚举\(x\)的部分提前,那么我们就需要考虑每个\(x\)的倍数i有多少个约数也是\(i\)的倍数,那么就是:\[ \sum_{i-1}^n\mu^2(i)\sum_{j-1}^{\lfloor n/i\rfloor}\sigma_0(j) \] 到这里做法就可以出来了,它是一个\(f(i)*g(\lfloor n/i\rfloor)\)的形式,所以我们可以对其除法分块,然后我们还要知道\(\mu^2\)和\(\sigma_0\)的前缀和,求\(\sigma_0\)的部分比较简单,可以直接枚举约数。\[ \sum_{i=1}^n\sigma_0(i)=\sum_{i=1}^m\lfloor \frac{n}{i}\rfloor \] 对于\(\mu^2\)的前缀和,我们可以考虑枚举每个平方因子进行容斥:\[ \sum_{i-1}^{\sqrt{n}}\mu(i) \times \lfloor \frac{n}{i^2}\rfloor \] 这样每个有平方因子的数刚好被算了0次,无平方因子的数刚好被算了一次。然后就是外层除法分块,内层也有一个除法分块和枚举平方因子求\(\mu^2\)和、\(\sigma_0\)的前缀和,我们可以通过一些预处理前缀和来降低后面枚举的复杂度。
代码
#include#include #define N 5000009using namespace std;typedef long long ll;const int maxn=5e6;int miu[N],prime[N],sum[N],d[N],ci[N];ll sumd[N];bool vis[N];inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x;}inline void prework(){ int k; miu[1]=1;d[1]=1; for(int i=2;i<=maxn;++i){ if(!vis[i]){prime[++prime[0]]=i;miu[i]=-1;ci[i]=1;d[i]=2;} for(int j=1;j<=prime[0]&&(k=i*prime[j])<=maxn;++j){ vis[k]=1;ci[k]=1;d[k]=2; if(i%prime[j]==0){ci[k]+=ci[i];d[k]=d[i]*(ci[k]+1)/ci[k];break;} miu[k]=-miu[i];d[k]=d[i]<<1; } } for(int i=1;i<=maxn;++i)sum[i]=sum[i-1]+miu[i]*miu[i],sumd[i]=sumd[i-1]+d[i];}inline ll calc(ll n){ if(n<=maxn)return sumd[n]; ll r,ans=0; for(ll l=1;l<=n;l=r+1){ r=n/(n/l); ans+=(n/l)*(r-l+1); } return ans;}inline ll calcsum(ll n){ if(n<=maxn)return sum[n]; ll ans=0; for(ll i=1;i*i<=n;++i){ ans+=(n/(i*i))*miu[i]; } return ans;}inline ll get(ll n){ ll ans=0;ll r; for(ll l=1;l<=n;l=r+1){ r=n/(n/l); ans+=calc(n/l)*(calcsum(r)-calcsum(l-1)); } return ans;}int main(){ int T=rd(); prework(); while(T--){ ll n=rd(); printf("%lld\n",get(n)); } return 0;}