Input The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases. In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).
Output For each test case, print a single line containing an integer, denoting the answer.
Sample Input 31 5 11 10 21 100 3
Sample Output 10482302 这题实质上就是分解质因数，不过不能对每个数都分解一次，这样肯定超时。 要用线性的方法求质因数。 设i可以分解为a1,a2,a3,a4……am,则总数加上（a1*k+1)*(a2*k+1)*……(am*k+1) #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #define ll long long using namespace std; #define ll long long const int mod=998244353; const int maxn=1000005; int prime[maxn]; bool vis[maxn]; int top; ll a[maxn]; ll b[maxn]; void pri() { top=0; memset(vis,0,sizeof vis); vis[1]=1; for(int i=2; i<maxn; i++) { if(!vis[i]) prime[top++]=i; for(int j=0; j<top&&i*prime[j]<maxn; j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } } void fun(ll l,ll r,ll k) { for(ll i=l; i<=r; i++) b[i-l]=i; for(ll i=l; i<=r; i++) a[i-l]=1; for(ll i=0; i<top&&prime[i]<=sqrt(r); i++) { ll x=l/prime[i]; if(x*prime[i]<l) x++; for(ll j=x; j*prime[i]<=r; j++) { ll s=0; while(b[prime[i]*j-l]%prime[i]==0) { s++; b[prime[i]*j-l]/=prime[i]; } a[prime[i]*j-l]=a[prime[i]*j-l]*(s*k+1)%mod; } } for(ll i=l; i<=r; i++) if(b[i-l]>1) a[i-l]=a[i-l]*(k+1)%mod; } int main() { pri(); int T; scanf("%d",&T); while(T--) { ll l,r; ll k; scanf("%lld%lld%lld",&l,&r,&k); ll sum=0; fun(l,r,k); for(ll i=l; i<=r; i++) sum=(sum+a[i-l])%mod; printf("%lld\n",sum); } return 0; } View Code
