思路：对于n^k其实就是每个因子的个数乘了一个K。然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法，总复杂度爆炸，就一直没过去，然后赛后看官方题解感觉好妙啊！通过类似素数筛法的方式，把L - R的质因子给分解，就可以在O(nlogn)的时间之内把所以的数给筛出来。
/* gyt
Live up to every day */ #include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e6+;
const ll maxm = 1e7;
const ll mod = ;
const int INF = 0x3f3f3f;
const ll inf = 1e15 + ;
const db eps = 1e-;
int is[maxn], pri[maxn];
ll f[maxn], num[maxn];
int cnt;
ll r, l, k; void prim() {
cnt=;
memset(is, , sizeof(is));
memset(pri, , sizeof(pri));
for (int i=; i<maxn; i++) {
if (!is[i]) {
pri[++cnt]=i;
for (int j=i+i; j<maxn; j+=i) {
is[j]=;
}
}
}
}
void solve() {
scanf("%lld%lld%lld", &l, &r, &k);
for (ll i=l; i<=r; i++) {
f[i-l+]=, num[i-l+]=i;
}
for (int i=; i<=cnt; i++) {
ll be=l+pri[i]-l%pri[i];
if (l%pri[i]==) be=l;
for (ll j=be; j<=r; j+=pri[i]) {
ll sum=;
while (num[j-l+]%pri[i]==) {
sum++;
num[j-l+]/=pri[i];
}
f[j-l+]=f[j-l+]*(k*sum%mod+)%mod;
}
}
ll ans=;
for (ll i=l; i<=r; i++) {
if (num[i-l+]!=) f[i-l+]=f[i-l+]*(k+)%mod;
ans=(ans+f[i-l+])%mod;
}
cout<<ans<<endl;
}
int main() {
int t = ;
//freopen("in.txt", "r", stdin);
scanf("%d", &t);
prim();
while(t--)
solve();
return ;
}
解释：
for (ll i=l; i<=r; i++) {
f[i-l+]=, num[i-l+]=i;
}
如果不进行这一步，那么数是1~1^12存不下，但是我们已知r-l<=1e6，这样就可以存下了。
f[i]表示当前的因数个数，num[i]，从l到r(下标1-(r-l+1))的数。
for (ll i=l; i<=r; i++) {
if (num[i-l+]!=) f[i-l+]=f[i-l+]*(k+)%mod;
ans=(ans+f[i-l+])%mod;
}
判断当前这个数还有没有素数因子。