公式：
上面的a|b表示a是b的约数，ai是每个质因数p分解后的项数
枚举每个x(l<=x<=r)
对于每个数暴力分解小于sqrt(r)的质数就好了， 因为大于sqrt(r)的质数最多只有一个，且对应的ai也只能为1
也就是说如果分解完那个数不是1的话就将d(x^k)乘上(k+1)
最后全加在一起
#include<stdio.h>
#include<math.h>
#define mod 998244353
#define LL long long
LL cnt, flag[1000005] = {1,1}, pri[1000005], val[1000005], d[1000005];
int main(void)
{
LL T, l, r, k, i, j, ans, sum;
for(i=2;i<=1000001;i++)
{
if(flag[i])
continue;
for(j=i*i;j<=1000001;j+=i)
flag[j] = 1;
pri[++cnt] = i;
}
scanf("%lld", &T);
while(T--)
{
ans = 0;
scanf("%lld%lld%lld", &l, &r, &k);
for(i=l;i<=r;i++)
val[i-l] = i, d[i-l] = 1;
for(i=1;pri[i]*pri[i]<=r;i++)
{
sum = l%pri[i];
j = (pri[i]-sum)%pri[i];
for(;j<=r-l;j+=pri[i])
{
sum = 0;
while(val[j]%pri[i]==0)
sum++, val[j] /= pri[i];
d[j] = d[j]*(sum*k+1)%mod;
}
}
for(i=0;i<=r-l;i++)
{
if(val[i]>1)
d[i] = (d[i]*(k+1))%mod;
ans = (ans+d[i])%mod;
}
printf("%lld\n", ans);
}
return 0;
}