先枚举素因子，再枚举区间，每次跨越素数长度
#include<bits/stdc++.h> using namespace std; typedef long long ll; int INF=0x3f3f3f3f; ll p[200005],cn=0,d[1000005]; ll aa[1000005],bb[1000005]; int main() { for(ll i=2; i<=1000000; i++) { if(d[i]==0) { p[cn++]=i; } for(int j=0; j<cn&&p[j]*i<=1000000; j++) { d[p[j]*i]=1; } } ll mod=998244353; // printf("%d\n",cn); int T; scanf("%d",&T); while(T--) { ll l,r,k,ans=0; scanf("%I64d%I64d%I64d",&l,&r,&k); if(l==1) ans++,l++; for(ll i=l;i<=r;i++) aa[i-l]=i,bb[i-l]=1; for(int i=0;i<cn;i++) { if(r<p[i])break; ll c=l/p[i]*p[i]; while(c<l) c+=p[i]; for(ll j=c;j<=r;j+=p[i]) { ll te=0; while(aa[j-l]%p[i]==0) { aa[j-l]/=p[i]; te++; } bb[j-l]=bb[j-l]*((te*k+1)%mod)%mod; } } for(ll i=l;i<=r;i++) { if(aa[i-l]!=1) bb[i-l]=(bb[i-l]*((k+1)%mod))%mod; ans=(ans+bb[i-l])%mod; } printf("%I64d\n",ans); } }