CC

自然万物都趋向从有序变得无序

0%

HDU 6069 Counting Divisors

发表于 更新于 分类于 Valine：

题目链接;点我

题目

In mathematics, the function d(n) denotes the number of divisors of positive integer n.

For example, d(12)=6 because 1,2,3,4,6,12 are all 12’s divisors.

In this problem, given l,r and k, your task is to calculate the following thing :

(∑i=lrd(ik))mod998244353

Input
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.

In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107)
.
Output
For each test case, print a single line containing an integer, denoting the answer.
Sample Input

3
1 5 1
1 10 2
1 100 3

Sample Output

10
48
2302

题意:

就如同那个公式写的,求质因子个数.

思路:

看到题目说质因子个数,我们就应该想到唯一分解定理. 我们知道数 n 的 唯一分解形式为: n = p1e1{p_1}^{e_1} * p2e2{p_2}^{e_2} … pnen{p_n}^{e_n}, 那么nkn^{k} 呢,自己分析几个例子可以看出 nkn ^{k} 实践上就是 n 的分解形式的 k 次方,于是我们只需要把指数变成这样: nkn^{k} = p1e1k{p_1}^{e_1 k} * p2e2k{p_2}^{e_2k} … pnenk{p_n}^{e_nk} 那么接下来我们就应该考虑怎么样分解,如果我们暴力枚举的话肯定是会超时的,因为区间中有很大素数,会拖慢我们的效率,于是我们想,能不能避免素数,然后我们想到类似素数筛法的原理,我们从2 到$\sqrt r $ 枚举每一个素数 p ,然后我们在 l 到 r 的范围内处理每一个之前枚举的这个素数的倍数 x , 看 每个 x 包含多少个p.最后剩下的没有被处理的就是质数.

代码:

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

typedef long long LL;
const int mod = 998244353;
const int maxn = 1e6 + 500;
int pri[maxn];
LL a[maxn],b[maxn];
bool vis[maxn];
LL r,l,k;
int  num;

void prime(){
    memset(vis,false , sizeof(vis));
    num = 0;
    for(int  i = 2; i < maxn ; ++i){
        if(!vis[i]) pri[++num] = i;
        for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
            vis[ i * pri[j]]  = true;
            if (i % pri[j] == 0) break;
        }
    }
}

int main()
{
    int T;
    prime();
    //freopen("1003.in", "r", stdin);
   // freopen("1003.txt", "w", stdout);
    scanf("%d", &T);
    while (T--)
    {
        LL ans = 0;
        scanf("%lld %lld %lld", &l, &r, &k);
       for(LL i = l; i <= r; ++i){
            a[i - l] = 1;
            b[i - l] = i;
       }for(int  i = 1 ; i <= num && pri[i] <= (int)sqrt((double) r); ++i){// 枚举素数.
            LL t = l / pri[i] * pri[i];//在 l 到 r 内处理这个素数的倍数.
            while(t < l) t += pri[i];
            while(t <= r){
               int cnt = 0;
               while(b[t-l] % pri[i] == 0){
                b[t-l] /= pri[i];
                cnt++;
               }a[t-l]  = (a[t-l] *(k * cnt + 1)) % mod;//储存每个数对应的因子个数.
               t += pri[i];
            }
       }for(LL i = l; i <= r; ++i)
            if(b[i-l] == 1)
                ans = (ans + a[i-l]) % mod;
                //否则这个数还是个素数.
            else ans = (ans + a[i-l]*(k + 1) % mod) % mod;
        printf("%lld\n",ans);
    }
    return 0;
}