题目链接
题意
对于给定的
l,r,k
求解
(∑i=lrd(ik))mod998244353
其中
d(n)
表示数字n的约数个数。
分析
根据欧拉定理可以得到对于一个数
n=pa11pa22pa33…pakk
,其中
pi
均为素数。则n的约数个数为
(a1+1)(a2+1)(a3+1)…(ak+1)
。而
nk
的约数个数就是
(a1k+1)(a2k+1)(a3k+1)…(akk+1)
。考虑到
r−l+1≤1e6
,尝试枚举
l−r
间的每个数。然而用所有素数去统计计算一个数的约数个数复杂度在
O(n√)
。转变思路想到枚举
1−1e6
之间的所有素数，通过筛法快速计算含有该素数因子的数，就能将复杂度缩减到可行范围内。具体过程请参考代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
int isprime[
1001000];
const int mod=
998244353;
vector<int> prime;
LL divi[
1001000];
LL res[
1001000];
int main(){
int T;
for(
int i=
2;i<=
1000;++i)
if(!isprime[i])
for(
int j=i*i;j<=
1000000;j+=i)
isprime[j]=
1;
for(
int i=
2;i<=
1000000;++i)
if(!isprime[i])
prime.push_back(i);
cin>>T;
while(T--){
LL l,r;
int k;
scanf(
"%I64d %I64d %d",&l,&r,&k);
for(
int i=
0;i<=r-l;++i){
res[i]=l+i;
divi[i]=
1;
}
for(
int i=
0;i<prime.size();++i){
if(prime[i]>r)
break;
LL st=(l+prime[i]-
1)/prime[i]*prime[i];
for(LL j=st;j<=r;j+=prime[i]){
int num=
0,idx=j-l;
while(res[idx]%prime[i]==
0){
num++;
res[idx]/=prime[i];
}
num=(num*k+
1);
divi[idx]=(divi[idx]*num)%mod;
}
}
LL ans=
0;
for(
int i=
0;i<=r-l;++i){
if(res[i]!=
1)
divi[i]=(divi[i]*(k+
1))%mod;
ans=(ans+divi[i])%mod;
}
printf(
"%I64d\n",ans);
}
}
