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