Counting Divisors
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1604 Accepted Submission(s): 592
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
1 5 1
1 10 2
1 100 3
Sample Output
10
48
2302
48
2302
Source
Recommend
/*
* @Author: Lyucheng
* @Date: 2017-08-03 13:13:45
* @Last Modified by: Lyucheng
* @Last Modified time: 2017-08-04 11:25:19
*/
/*
题意：给你一个区间[l,r]让你求区间内每个数的k次方因子数的总和 思路：比赛的时候想出来 i^k的因子是 (n1*k+1)*(n2*k+1)*...*(np*k+1),但是没想出来怎么优化，素数枚举
很烦，四场比赛每次差一点，比赛的时候想的是枚举[l,r]之间的数，优化到8300ms,实在没法优化了，应
该反过来想，枚举从[l,r]的素因子，因为i素因子的个数远小于i,大多数在sqrt i内，最多只有一个在sqrt i
之外。
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h> #define LL long long
#define mod 998244353
#define MAXN 1000005 using namespace std; int t;
LL l,r,k;
LL res;
LL d[MAXN];
LL pos[MAXN];
bool prime[MAXN];
LL p[MAXN];
int tol;
void init(){
tol=;
for(int i=;i<MAXN;i++){
prime[i]=true;
}
prime[]=prime[]=false;
for(int i=;i<MAXN;i++){
if(prime[i])
p[tol++]=(LL)i;
for(int j=;j<tol&&i*p[j]<MAXN;j++){
prime[i*p[j]]=false;
if((LL)i%p[j]==) break;
}
}
} int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
init();
scanf("%d",&t);
while(t--){
res=;
scanf("%I64d%I64d%I64d",&l,&r,&k);
for(LL i=l;i<=r;i++){
d[(int)(i-l)]=;
pos[(int)(i-l)]=i;
}
for(int i=;i<tol;i++){//枚举所有的素数
if(p[i]<=) continue;
LL cnt=(l+p[i]-)/p[i]*p[i];//找出[l,r]区间内的第一个p[i]的倍数
if(cnt-l<||cnt-l>r-l) continue;
for(int j=cnt-l;j<=r-l;j+=p[i]){
LL cur=;
while(pos[j]&&pos[j]%p[i]==){
cur++;
pos[j]/=p[i];
}
d[j]*=(cur*k+);
d[j]%=mod;
}
}
for(int i=;i<=r-l;i++){
if(pos[i]==)
res+=d[i];
else
res+=d[i]*(k+);
res%=mod;
}
printf("%I64d\n",res);
}
return ;
}