HDU6069:Counting Divisors(因子数统计|区间筛)

题意

计算\(\sum_{i=l}^kd(i^k)(d_i代表i的因子数）\)

分析

比赛搞了3个小时都没搞出来，有两个思维上的trick

1.要先遍历素数，再遍历[L,R]，而不是枚举每个数，然后对每个数进行质因数分解

2.比赛的时候我有想过枚举素数，但是忘记因子计算公式可以分开相乘，而不用一次性求粗来，导致我们队的崩盘，我要背锅！！！

具体的做法：枚举每个素数，并枚举[L,R]中的素数的倍数，对于每个倍数，统计因子个数,用b[i]代表第i个数的因子数，具体键代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

const ll mod = 998244353;

const int maxn=1000000;

int prime[maxn+10];

bool p[maxn+10];

inline void get_prime()

{

   F(i,2,maxn)

   {

      if(!p[i]) prime[++prime[0]]=i;//prime[0]存储1~maxn的质数个数

      for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;++j)

      {

         p[i*prime[j]]=1;

         if(i%prime[j]==0) break;

      }

   }

}

int t;

ll L,R,K,ans;

ll a[maxn+10],b[maxn+10];//a数组存储对于每个质数除后的数，b数组存放i的因子个数

void calc()

{

    int len=R-L+1;

    R(i,0,len) a[i]=i+L,b[i]=1;

    for(int i=1;prime[i]*1LL*prime[i]<=R;++i)

    {

        ll x=prime[i],k=L/x*x,cnt;

        if(k<L) k+=x;

        for(;k<=R;k+=x) if(a[k-L]%x==0)

        {

            cnt=0;

            while(a[k-L]%x==0) cnt++,a[k-L]/=x;

            cnt=cnt*K+1;

            b[k-L]=b[k-L]*cnt%mod;

        }

    }

    ans=0;

    //R(i,0,len) printf("%I64d%c",a[i],i==len-1?'\n':' ' );

    R(i,0,len)

    {

        if(a[i]!=1) b[i]=b[i]*(K+1)%mod;

        //printf("%I64d%c",b[i],i==len-1?'\n':' ' );

        ans=(ans+b[i])%mod;

    }

}

int main()

{

    get_prime();

    for(scanf("%d",&t);t--;)

    {

        scanf("%lld %lld %lld",&L,&R,&K);

        calc();

        printf("%I64d\n",ans );

    }

    return 0;

}

巴特西

HDU6069:Counting Divisors(因子数统计|区间筛)

最新文章

热门文章