思路：
AC代码：
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define ll long long #define endl (" ") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ft (frist) #define sd (second) #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e6+10000; const ll mod=998244353; ll l,r,k,num[N],ans[N]; ll p[N]; bool isprime[N]; ll get_prime(){ ll c = 0,n=N-1000; memset(isprime, true,sizeof(isprime)); isprime[1] = 0; for(ll i=2; i<=n; i++){ if(isprime[i]){ p[++c] = i; for(ll j=i*i; j<=n; j+=i) isprime[j] = false; } } return c; } int main(){ ll c=get_prime(); //for(int i=1; i<=100; ++i) cout<<p[i]<<" "; int T=15,f; scanf("%d",&T); while(T--){ //l=1e12-1e6, r=1e12,k=1e6; scanf("%lld %lld %lld",&l, &r, &k); for(ll i=l; i<=r; ++i){ num[i-l+1]=i; ans[i-l+1]=1; } for(ll j=1; j<=c && p[j]<=r; ++j){ if(l%p[j]==0) f=1; else f=(l/p[j]+1)*p[j]-l+1; for(ll t=f; t<=r-l+1; t+=p[j]){ ll d=0; while(num[t]%p[j]==0){ num[t]/=p[j]; d++; } ans[t]=(ans[t]*(((d*k)%mod)+1))%mod; } } ll anss=0; for(ll i=1; i<=r-l+1; ++i){ if(num[i]!=1) ans[i]=(ans[i]*(k+1))%mod; anss=(anss+ans[i])%mod; } printf("%lld ",anss); } return 0; }