原题链接 hud 6069 题目大意：题目上给出 l ， r ，k 求从 l 到 r 范围内 i 的 k次方的所有约数个数的和。 解题思路：因为题目上给的 l ，r，和 k 的值比较大，不能直接暴力求解，要用到数学上的一个知识点 约数定理: 对于一个大于1的整数n，可以分解质因数n = p1^a1 * p2^a2 * p3^a3 · ·· ··· pn^an，其中p1，p2，……pn为质数，而约数个数为d = (a1+1)(a2+1)(a3+1)…(ak+1)。 类推可以得到n^k =p1^k * a1 * p2^k * a2 * p3^k * a3 · ·· ··· pn^k * an， 的约数个数为(k *a1+1)(k *a2+1)(k *a3+1)…(k *ak+1) 所以对于这个题而言，我们首先需要用筛法将出sqrt（r）以内的素数打表，再枚举区间[l,r]中所有p的倍数，将其分解质因数，利用约数定理求出约数个数 code
#include <bits/stdc++.h> #define N 1000005 #define mod 998244353 using namespace std; long long priem[N],a[N],p[N]; map<long long,long long> m; int id; long long vis[N]; void Init() { id = 0; memset(vis,-1,sizeof(vis)); vis[0] = vis[1] = 0; for(int i=2;i<N/2;i++) if(vis[i]) { priem[id++] = i; for(int j = i+i;j<N;j+=i) vis[j] = 0; } } int main() { int T;scanf("%d",&T); Init(); while(T--){ long long l,r,k; scanf("%lld %lld %lld",&l,&r,&k); long long sum = 0; if(l==1) l++,sum++; for(long long int i=0;i<=r-l;i++)a[i] = 1,p[i]=l+i; for(long long int i = 0;priem[i]*priem[i]<=r;i++) { for(long long j = (l/priem[i]+(l%priem[i]!=0))*priem[i];j<=r;j+=priem[i])///注意这里j的初始值，必须一次性定位到l-r之间否则会超时 { long long temp = 0; while(p[j-l]%priem[i]==0) { p[j-l]/=priem[i]; temp++; } a[j-l] = (a[j-l]*((temp*k)%mod +1))%mod; } } for(int i=0;i<=r-l;i++){///因为最后p[j-i]的值可能为1还可能为一个素数，所以如果为1的话就直接加上a[i],否则要用约数定理求出约数个数 if(p[i]==1) sum = (sum+a[i])%mod; else sum = (sum+a[i]*(k+1))%mod; } printf("%lld\n",sum); } return 0; }