思路：n=p1^x1*p2^x2....pm^xm，则p的约数个数为(x1+1)*(x2+1)....(xm+1)，那么n^k=p1^(x1+k)....pm^(xm+k),约数个数为(x1*k+1)*....*(xm*k+1)。
先求出1-1e6内的质数，再对l--r之间的数求xi
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e6+10; 5 const ll mod=998244353; 6 7 ll prime[N],vis[N]; 8 9 int init(){ 10 int x=0; 11 for(ll i=2;i<=N;i++){ 12 if(!vis[i]) { 13 // cout<<i<<endl; 14 prime[++x]=i; 15 } 16 else continue; 17 for(ll j=i*i;j<=N;j+=i){ 18 vis[j]=1; 19 } 20 } 21 return x; 22 } 23 ll a[N],b[N]; 24 int main(){ 25 int t; 26 ll l,r,k; 27 int len=init(); 28 scanf("%d",&t); 29 while(t--){ 30 scanf("%lld%lld%llld",&l,&r,&k); 31 for(int i=0;i<=N-1;i++){ 32 a[i]=b[i]=1; 33 } 34 for(int i=1;i<=len;i++){ 35 ll p=prime[i];ll L; 36 if(l%p!=0) L=(l/p+1)*p; else L=l; 37 for(ll j=L;j<=r;j+=p){ 38 ll x=0; 39 ll base=1, y=j; 40 while(y%p==0){ 41 x++; 42 y/=p; 43 base*=p; 44 } 45 a[j-l+1]=a[j-l+1]*(x*k+1)%mod; 46 b[j-l+1]*=base; 47 48 } 49 } 50 ll sum=0; 51 for(ll i=l;i<=r;i++){ 52 if(b[i-l+1]!=i) 53 a[i-l+1]=a[i-l+1]*(k+1)%mod; 54 sum=(sum+a[i-l+1])%mod; 55 } 56 printf("%lld ",sum); 57 } 58 }