hdu 6069Counting Divisors 數學

Counting Divisors

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description 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
        

Source 2017 Multi-University Training Contest - Team 4

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	
	public static void main(String[] args) {
		new Task().solve();
	}
}



class Task {
	InputReader in = new InputReader(System.in) ;
	PrintWriter out = new PrintWriter(System.out) ;
	final int N = 1000000 ;
    long[] prime = new long[N+1] ;
    int primeCnt ;
    boolean[] vis = new boolean[N+1] ;
    {
    	Arrays.fill(vis, false) ;
    	primeCnt = 0 ; 
    	for(int i = 2 ; i <= N ; i++){
    		if(! vis[i]){
    			prime[primeCnt++] = (long)i ;
    		}
    		for(int j = 0 ; j < primeCnt && prime[j] * i <= N ; j++){
    			vis[(int)(i*prime[j])] = true ;  
    			if(i % prime[j] == 0){
    				break ;
    			}
    		}
    	}
    }
    
    final long Mod = 998244353L ;
    
    long calc(long L , long R , long k){  
        int len = (int)(R - L + 1) ;
        long[] num = new long[len] ;
        long[] sum = new long[len] ;
        for(int i = 0 ; i < len ; i++){
        	num[i] = L + i ;
        	sum[i] = 1 ;
        }
        for(int i = 0 ; i < primeCnt && prime[i]*prime[i] <= R ; i++){  
            long start = L/prime[i]*prime[i] ;  
            if(start < L)  
                start += prime[i] ;  
            for(long j = start ; j <= R ; j += prime[i]){  
                int idx = (int)(j - L) ; 
                if(num[idx] % prime[i] == 0){
	                long t = 0 ;
                	while(num[idx] % prime[i] == 0){
	                	num[idx] /= prime[i] ;
	                	t++ ;
	                }
                	sum[idx] *=  (t*k + 1) ;
                	sum[idx] %= Mod ;
                }
            }
        }  
        long reslut = 0 ;
        for(int i = 0 ; i <= R-L ; i++){  
        	if(num[i] != 1){
        		sum[i] *= (k+1) ;
        		sum[i] %= Mod ;
        	}
        	reslut += sum[i] ;
        	reslut %= Mod ;
        }
        return reslut ;  
    }  
	
	void solve(){
		int t = in.nextInt() ;
		while(t-- > 0){
			out.println(calc(in.nextLong(), in.nextLong(), in.nextLong())) ;
		} 
		out.flush() ;
	}
}

class InputReader {    
    public BufferedReader reader;    
    public StringTokenizer tokenizer;    
    
    public InputReader(InputStream stream) {    
        reader = new BufferedReader(new InputStreamReader(stream), 32768);    
        tokenizer = new StringTokenizer("");    
    }    
    
    private void eat(String s) {    
        tokenizer = new StringTokenizer(s);    
    }    
    
    public String nextLine() {     
        try {    
            return reader.readLine();    
        } catch (Exception e) {    
            return null;    
        }    
    }    
    
    public boolean hasNext() {    
        while (!tokenizer.hasMoreTokens()) {    
            String s = nextLine();    
            if (s == null)    
                return false;    
            eat(s);    
        }    
        return true;    
    }    
    
    public String next() {    
        hasNext();    
        return tokenizer.nextToken();    
    }    
    
    public int nextInt() {    
        return Integer.parseInt(next());    
    }    
    
    public int[] nextInts(int n) {    
        int[] nums = new int[n];    
        for (int i = 0; i < n; i++) {    
            nums[i] = nextInt();    
        }    
        return nums;    
    }    
    
    public long nextLong() {    
        return Long.parseLong(next());    
    }    
    
    public double nextDouble() {    
        return Double.parseDouble(next());    
    }    
    
    public BigInteger nextBigInteger() {    
        return new BigInteger(next());    
    }    
    
}