hdu6069 Counting Divisors 質因數分解 區間篩

http://acm.hdu.edu.cn/showproblem.php?pid=6069

Counting Divisors

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

Total Submission(s): 2757    Accepted Submission(s): 1020

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   題意：d[i]：表示i的所有因子個數。現在求∑d(i^k)，i∈[l,r]。 題解：首先每個數都可以分解成：i=p1^c1*p2^c2*...*pn^cn，其中p1，p2，...，pn均為質數。那麼d[i]就可以表示成(p1+1)*(p2+1)*...*(pn+1)，是以d[i^k]=(p1*k+1)*(p2*k+1)*...*(pn*k+1)。是以本題先對素數打表，但是直接枚舉l-r仍然會逾時。可以反過來枚舉每個質數，用篩法的方式去枚舉質數的每個倍數，這樣就比原來快多了。 代碼：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 1000000 + 5;
const LL mod = 998244353;
int primes[N],tot=0,t;
LL l,r,k;
LL num[N],ans[N];
bool isPrime[N];

void getPrime()//素數篩 
{
    mem(isPrime,true);
    for(int i=2;i<N;i++)
    {
        if(isPrime[i])
            primes[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            if(i*primes[j]>=N) break;
            isPrime[i*primes[j]]=false;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
	getPrime();
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld%lld",&l,&r,&k);
		LL n=(r-l+1);
		for(int i=0;i<n;i++){//儲存每個數字和其貢獻值 
			num[i]=i+l;
			ans[i]=1;
		}
		for(int i=1;(LL)primes[i]*primes[i]<=r;i++){//枚舉每個素數 
			for(LL j=primes[i]*(l/primes[i]);j<=r;j+=primes[i]){//枚舉每個素數的倍數 
				if(j<l){
					continue;
				}
				LL cnt=0;
				while(num[j-l]%primes[i]==0){
					cnt++;
					num[j-l]/=primes[i];
				}
				ans[j-l]=(ans[j-l]*(1LL+cnt*k))%mod;
			}
		}
		LL sum=0;
		for(int i=0;i<n;i++){
			if(num[i]>1){//表示num[i]本身就是素數 
				ans[i]=(ans[i]*(1LL+k))%mod;
			}
			sum=(sum+ans[i])%mod;
		}
		printf("%lld\n",sum);
	}
	return 0;
}