JS's Blog
0%

Hdu 6069 - Counting Divisors（区间筛质因子）

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6069

题目大意：
给定区间[l,r][l,r]和kk，$$d(i) = \sum_{d=1,d|n}{n}1$$求式子$$\sum_{i=l}{r}d(i^k)$$的值，结果对998244353取模

分析：
区间长度为1e6，数据有10组以上，暴力分解整个区间的话，每个数的分解至多是logn级别的，而基于Miller_Robin的质因数分解polard_rho也只是O(n14)O(n^{\frac{1}{4}})级别的，远远达不到要求，所以不能从对每个数分解质因数上想，而是试着用[2,r][2,\sqrt r]内的所有质因子去筛[l,r][l,r]区间内的数，最后在除尽了这些因子后的数，要么是1，要么是一个大的质因子，且次数至多为1，因为如果大于sqrtrsqrt r的因子次数大于1，这个数的大小就会大于rr，产生矛盾

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;


const ll mod = 998244353;
const int maxn = 1e6+100;

ll l,r,k;
int len;
bool isprime[maxn+200];
int prime[maxn];



ll divi[maxn];
ll cnt[maxn];

void init()
{
    for (int i =2 ; i <= maxn; i ++)
    {
        if (!isprime[i])
        {
            prime[++prime[0]] = i;
            for (int j = i +i ; j <= maxn ; j+= i)
                isprime[j] = true;
        }
    }
}

void solve()
{
    int st;
    for (int i = 1 ; prime[i]<= r/prime[i] && i<= prime[0] ; i ++)
    {
        //printf("i = %d\n",prime[i]);
        if (l%prime[i]==0)
            st = 1;
        else
            st = 1 + (prime[i]-l%prime[i]);
        for (int j = st ; j <= len ; j +=prime[i])
        {
            int ct = 0;
            while (divi[j]%prime[i]==0)
            {
                divi[j]/=prime[i];
                ct++;
            }
            cnt[j]*=(ct*k+1);
            if (cnt[j]>=mod)
                cnt[j] %= mod;
        }
    }
    ll ans = 0;
    for (int i =1 ; i <= len ; i ++)
    {
        if (divi[i]!=1)
            cnt[i] = cnt[i] * (k+1)%mod;
        //printf("divi[%d] = %lld\n",i,divi[i]);
        ans += cnt[i];
        if (ans>=mod)
            ans %= mod;
    }
    printf("%lld\n",ans);
}


int main()
{
    init();
    //printf("prime[0] = %d\n",prime[0]);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld%lld",&l,&r,&k);
        len = (int)(r- l +1);
        for (int i = 1 ; i <= len ; i ++)
        {
            divi[i] = l + i -1;
            cnt[i] = 1;
        }

        solve();



    }
    return 0;
}