HDU6069（数学）-蒲公英云

HDU6069（数学）

题目链接：hdu6069

题目大意：

给你三个数l,r,k (1≤l≤r≤10^12,r−l≤10^6,1≤k≤10^7)求 :

(∑i=lrd(ik))mod998244353

题目思路:

首先我们很好想到的是枚举区间[l,r] ,然后对于每个i我们分解因子，但是这样做的复杂度是(r-l+1)*sqrt(r) 已经超时了，
所以我们要去优化分解因子，这里我们筛选出1e6内的质数，然后拿质数去枚举区间，这样就可以避免重复分解同样的因子，然后
就是怎么求d(i^k),根据约数定理得到d(i^k) = (1+x1*k)*(1+x2*k)*... x1,x2..为i分解后因子的个数,所以我们可以
用个数组保存每个i的答案最后加起来就是

AC代码：

#include<bits/stdc++.h>
using namespace std;
const long MAXP = 1000000;
long prime[MAXP] = {
   0},num_prime = 0;
long long d[1000005],v[1000005];
int isNotPrime[MAXP] = {
   1, 1};
#define mod 998244353
int main()
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
                break;
        }
    }
    int t;cin>>t;
    while(t--)
    {
        long long l,r,k;
        scanf("%lld%lld%lld",&l,&r,&k);
        for(long long i=0;i<r-l+1;i++)
        {
            d[i] = 1;
            v[i] = l+i;
        }
        long long ans = 0;
        long long cnt = 0;
        for(int i=0;i<num_prime;i++)
        {
            if(prime[i]>r)break;
            long long x = l/prime[i]*prime[i];
            if(x<l)x+=prime[i];
            long long y = 0;
            while(x+y*prime[i]<=r)
            {
                cnt++;
                long long xx = x+y*prime[i],cnt1 = 0;
                y++;
                int id = xx-l;
                while(v[id]%prime[i]==0)
                {
                    cnt1++;
                    v[id]/=prime[i];
                }
                d[id]*=(1+k*cnt1);
                d[id]%=mod;
            }
        }
        for(long long i=0;i<r-l+1;i++)
        {
            if(v[i]!=1)
            {
                ans = (ans+(d[i]*(1+k))%mod)%mod;
            }
            else
            {
                ans = (ans+d[i])%mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}