SP34096 【DIVCNTK - Counting Divisors (general)】

题目

求

\[\sum_{i=1}^n \sigma(i^k)
\]

我们先来设一个函数\(f(i)=\sigma(i^k)\)

根据约数个数定理

\[f(p)=\sigma(p^k)=k+1
\]

\[f(p^c)=\sigma(p^{ck})=ck+1
\]

这不就可以Min_25筛了吗

还是先求出来一个区间内的质数个数，一个质数的贡献显然是\(k+1\)，之后上板子就好了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define maxn 3000005

#define re register

#define LL unsigned long long

int T,tot,f[maxn];

LL n,K,p[maxn],w[maxn],id1[maxn],id2[maxn],m,Sqr,g[maxn];

inline LL S(LL x,int y) {

    if(x<=1||p[y]>x) return 0;

    int t=(x<=Sqr)?id1[x]:id2[n/x];

    LL ans=g[t]*(K+1)-(K+1)*(y-1);

    for(re int k=y;k<=tot&&p[k]*p[k]<=x;k++) {

        LL p1=p[k];

        for(re int e=1;p1<=x;e++,p1*=p[k])

            ans+=(S(x/p1,k+1)+((e>1)?1:0))*(K*e+1);

    }

    return ans;

}

int main()

{

    scanf("%d",&T);f[1]=1;

    for(re int i=2;i<=100000;i++) {

        if(!f[i]) p[++tot]=i;

        for(re int j=1;j<=tot&&p[j]*i<=100000;j++) {

            f[p[j]*i]=1;if(i%p[j]==0) break;

        }

    }

    while(T--) {

        scanf("%llu%llu",&n,&K);Sqr=std::sqrt(n)+1;m=0;

        for(re LL l=1,r;l<=n;l=r+1) {

            r=n/(n/l);w[++m]=n/l;

            if(w[m]<=Sqr) id1[w[m]]=m;

                else id2[n/w[m]]=m;

            g[m]=w[m]-1;

        }

        for(re int j=1;j<=tot&&p[j]*p[j]<=n;j++)

            for(re int i=1;i<=m&&p[j]*p[j]<=w[i];i++) {

                int k=(w[i]/p[j]<=Sqr)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];

                g[i]=g[i]-g[k]+j-1;

            }

        printf("%llu\n",S(n,1)+1);

    }

    return 0;

}