# HDU 6069 Counting Divisors （素数）

## 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 :

$$(\sum_{i=l}^{r}d(i^k))~mod~998244353$$

## 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≤10^{12},r−l≤10^6,1≤k≤10^7)$ .

## 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


## 思路

SPOJ 中有两道类似的题目，其中一个 k = 2 ，另一个 k = 3 ，然后区间长度最大为 $10^{12}$ ，用到了杜教筛洲阁筛

## AC 代码

#include<bits/stdc++.h>
using namespace std;

typedef __int64 LL;
const int maxn = 1e6+10;
const int mod = 998244353;
LL prime[maxn],tot;
bool visit[maxn];
LL l,r,k;
LL num[maxn],sum[maxn];

void getprime()
{
tot=0;
memset(visit,0,sizeof(visit));
for(int i=2; i<maxn; i++)
{
if(!visit[i])
{
prime[tot++]=i;
for(int j=i+i; j<maxn; j+=i)
visit[j]=1;
}
}
}

void solve()
{
for(int i=0; i<=r-l; i++)
{
sum[i]=1;
num[i]=i+l;
}
for(int i=0; prime[i]*prime[i]<=r; i++)
for(LL j=(l/prime[i]+(l%prime[i]?1:0))*prime[i]; j<=r; j+=prime[i])
if(j>=l)
{
LL res=0;
while(num[j-l]%prime[i]==0)
{
num[j-l]/=prime[i];
res++;
}
sum[j-l]=sum[j-l]*(res*k+1)%mod;
}
LL ans=0;
for(int i=0; i<=r-l; i++)
{
if(num[i]>1)
sum[i]=sum[i]*(k+1)%mod;
ans=(ans+sum[i])%mod;
}
cout<<ans<<endl;
}

int main()
{
getprime();
int T;
while(cin>>T)
{
for(int i=0; i<T; i++)
{
cin>>l>>r>>k;
solve();
}
}
return 0;
}