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;  
    }  
}