Counting Divisors
time limit per test 5 second memory limit per test 256 megabytes
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=l~r d(i^k))mod 998244353

传送门:HDU6069

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≤1e12,r−l≤1e6,1≤k≤1e7).

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

1
2
3
4
3
1 5 1
1 10 2
1 100 3

Sample Output

1
2
3
10
48
2302

题解

二次素筛 在素筛的同时统计因数个数 注意4*(1e9+7)这种特殊情况 4被筛掉了 但1e9+7还在 所以要记录筛到最后的结果
## AC code:(不包含输入类)
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
import java.io.*;  
import java.util.*;
public class Main {
static ArrayList<Integer>list1;
static boolean[]prime;
static boolean[]twiceprime;
static long[]js;
static long[]shu;
static long mod=998244353;
static long z;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
list1=new ArrayList<Integer>();
prime=new boolean[(int) (1e6+100)];
makePrime((int)(1e6+50));
for(int i=2;i<1e6+5;i++){
if(prime[i])list1.add(i);
}
int t=sc.nextInt();
while(sc.hasNext()){
long l=sc.nextLong();
long r=sc.nextLong();
z=sc.nextLong();
js=new long[(int) (r-l+1)];
shu=new long[(int) (r-l+1)];
for(int i=0;i<=r-l;i++)shu[i]=i+l;
Arrays.fill(js, 1);
makePrimeTwice(l,r); //利用1e6的素数二次筛
long sum=0;
for(long i=l;i<=r;i++){
//pw.println(js[(int) (i-l)]);
if(!twiceprime[(int) (i-l)]){
if(shu[(int) (i-l)]==1)
sum=(sum+js[(int) (i-l)])%mod; //如果最后筛完了
else
sum=(sum+js[(int) (i-l)]*(z+1))%mod;
}
else{
sum=(sum+(z+1))%mod;
}
}
pw.println(sum%mod);
pw.flush();
}

}
static void makePrime(int n){ //素数筛法
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;
for(int i=2;i<=1050;i++){
if(prime[i]){
for(int j=i*i;j<=n+1;j+=i){
prime[j]=false;
}
}
}
}
static void makePrimeTwice(long l,long r){
twiceprime=new boolean[(int) (r-l+1)];
Arrays.fill(twiceprime, true);
long k=0;
for(int i=0;i<list1.size();i++){
long temp=list1.get(i);
k=l/temp; //important
while(k*temp<l||k<=1) k++;
for(long j=k*temp;j<=r;j+=temp){
if(j>=l){
twiceprime[(int) (j-l)]=false;
long count=0;
while(shu[(int) (j-l)]%temp==0){
shu[(int) (j-l)]/=temp; //记录筛的结果
count++;
}
js[(int) (j-l)]=(js[(int) (j-l)]%mod*((count%mod*z%mod+1)))%mod;
}
}
}
if(l==1)twiceprime[0]=false;
}
}