对于 $30$ 分直接暴力计算即可。

在过程中可以发现，这个问题最耗费时间的部分就是计算因子，那么思考一个数字的因子个数可以怎么计算？

显然是通过计算出这个数字的所有质因子个数，然后进行排列组合。

设 $x=p_1^{c_1} p_2^{c_2} \ldots p_m^{c_m}$。

那么 $x$ 的因子个数就是 $(c_1+1) * (c_2+1) * (c_3+1) \dots * (c_m+1)$。

由于这里是 $x^n$ 所以因子个数就是 $(n * c_1+1) * (n * c_2+1) * (n * c_3+1) \dots * (n * c_m+1)$。

所以对每个数字只要考虑进行质因数分解即可，这里可以提前进行筛法求出 $100w$ 以内的所有质数，那么这样可以通过 $60$ 分。

接着考虑如何继续优化，显然对于一个数字 $i$，需要枚举所有质数判断能否被 $i$ 整除这一步会花费不少的时间，那么我们可以考虑反过来思考：

对于每个质数 $p[j]$，直接枚举这个质数 $p[j]$ 的所有倍数对 $p[j]$ 进行质因数分解，这样就可以优化掉一些无意义的枚举。

但是这显然还不够，由于数字范围有 $100w$，要枚举的质数数量也很多。

那么考虑一个问题，就是显然在质因数分解的过程中，有很多大质数只会出现 $1$ 次。

所以显然我们可以考虑只枚举 $\sqrt{r}$ 范围内的质数，进行以上质因数分解。

在所有数字质因数分解完后，如果某个数字最后不为 $1$ 就说明它有一个大于 $\sqrt{r}$ 的质因子，最后计算答案的时候多乘一个 $(k+1)$ 进去即可。

题面解析

$fun(x)$ 指 $x$ 有多少个因数。
题目要求的是：算 $\sum_{i=l}^{r} fun(i^n)$

第一步：一个数的因数个数fun(x)怎么算？

对于一个$x$，他的质因数分解为：

$$x = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k }$$

因数个数（本题的 $fun$）：

$$fun(x) = (a_1+1)(a_2+1)\cdots(a_k+1)$$

为什么？因为任何因数都是类似"选一些 2，再选一些 3"拼出来的：
比如$12$：$12=2×2×3$
$2$ 可以选 $0$ 个、$1$ 个、$2$ 个 -> $3$ 种
$3$ 可以选 $0$ 个、$1$ 个 -> $2$ 种
组合起来 $3×2=6$ 种，就是 $6$ 个因数。

那 $x$ 的 $n$ 次方呢？

$$x^n = (p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k})^n = p_1^{na_1} \times p_2^{na_2} \times \cdots \times p_k^{na_k}$$

两者结合，得到本题答案公式

$$fun(x^n) = (na_1+1)(na_2+1)\cdots(na_k+1)$$

第二步：如何因式分解？

数据范围说 $r$ 可以到 $10^{12}$，区间里有最多 $10^6$ 个数。普通分解的方法直接炸飞了。

所以，我们考虑反过来看：不是问"每个数有哪些质因子"，而是问"每个质数能整除区间里的哪些数"。

具体做法

先筛出 $10^6$ 以内的所有质数。
给区间里每个数准备两个数组：
$cur[i]$：这个数还没被除掉的部分
$ans[i]$：当前的因数个数
对于每个小质数 $p$：
找到第一个 $\ge l$ 的 $p$ 的倍数 $s$ ($\lceil l/p \rceil \times p$)；
从 $s$ 开始每次 $+p$，扫过区间内所有 $p$ 的倍数 $j$；
对每个 $j$，把 cur 里的 $p$ 全部除尽，记下除了多少次，设为 $e$；
按公式往 ans 里乘上 $(e \times n + 1)$。

最后收尾，使用前面的公式乘起来就可以了，需注意：cur>1 的是大素数，指数为 1，乘 (n+1) 即可。

代码（附注释）

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
const int MOD=1e9+7;
const int MAXP=1e6;

int l,r,n;
int cur[N];//cur[i]=i-l 还没被除掉的部分
int ans[N];//ans[i]=fun((i-l)^n) 因数个数
bool vis[N];//素数标记
int prm[N],tot;//素数表

signed main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);

    cin>>l>>r>>n;
    for(int i=l;i<=r;i++) cur[i-l]=i,ans[i-l]=1;//初始化
    //筛素数
    for(int i=2;i<=MAXP;i++){
        if(!vis[i]){
            prm[++tot]=i;
            for(int j=i*i;j<=MAXP;j+=i) vis[j]=1;
        }
    }
    //对每个小素数x，直接枚举它在[l,r]里的所有倍数
    for(int k=1;k<=tot;k++){
        int x=prm[k];
        int st=((l+x-1)/x)*x;//st是第一个>=l的x的倍数
        for(int j=st;j<=r;j+=x){//每隔x跳一步，扫过区间内所有x的倍数
            int id=j-l;//j在数组里的下标
            if(cur[id]%x) continue;//x已经被除干净了，跳过
            int e=0;
            while(cur[id]%x==0){cur[id]/=x;e++;}//把x除尽，统计指数e
            ans[id]=ans[id]*((e*n%MOD+1)%MOD)%MOD;//公式
        }
    }
    
    int sum=0;
    for(int i=0;i<=r-l;i++){
        if(cur[i]>1) ans[i]=ans[i]*((n%MOD+1)%MOD)%MOD;//还剩cur>1的，必是>1e6的素数（指数为1），补乘(n+1)
        sum=(sum+ans[i])%MOD;
    }
    cout<<sum<<'\n';
}

题解

关键注意力

若正整数 $r$ 存在一个因子 $x$ ，使得 $x > \sqrt{r}$，则 $x=r$ 且 $r$ 为质数。

由此得出一个在 $(10^{6},10^{12}]$ 之间的正整数 $r$，最多有一个大于 $10^6$的质因子。

计数公式
若 $i=\prod p_j^{a_j}$，则

$$fun(i)=\prod(a_j+1)$$

化为

$$fun(i^n)=\prod(a_j n+1)$$

十分显然。

做法：区间筛质因数

1. 筛出 $1\sim 10^6$ 的质数。
2. 对每个质数 $p$，枚举 $[l,r]$ 中 $p$ 的倍数，除尽并统计指数 $c$，累乘 $c\cdot n+1$。
3. 最后若剩余 $>1$，说明还有一个 $>10^6$ 的质因子，指数为 $1$，再乘 $n+1$。
4. 求和取模。

复杂度
$O((r-l)\log\log r)$，空间 $O(r-l+10^6)$。

代码

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int N=1e6+500,MOD=1e9+7;
bool is[N];
LL l,r,n,sy[N],dp[N],ans=0;
LL ys[N];

LL fpow(LL a,LL b){
	LL res=1;
	while(b){
		if(b&1){
			res=(res*a)%MOD;
		}
		a=(a*a)%MOD;
		b/=2;
	}
	return res;
}

int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin>>l>>r>>n;
	for(int x=0;x<=r-l;x++){
		dp[x]=1;
		sy[x]=x+l;
		ys[x]=0;
	}
	memset(is,1,sizeof(is));
	for(int x=2;x<=1000000;x++){
		if(is[x]){
			for(int y=2;1000000/x>=y;y++){
				is[x*y]=0;
			}
			LL t=x;
			for(LL i=l/t;i<=r/t;i++){
				if(i*t>=l && i*t<=r){
					LL q=i*t,ct=0;
					while(sy[q-l]%t==0){
						sy[q-l]/=t;
						ct=(ct+1)%MOD;
					}
					dp[q-l]=(dp[q-l]*(ct*n+1))%MOD;
					//cout<<q<<" has "<<t<<" * "<<ct-1<<endl;
					ys[q-l]++;
				}
			}
		}
	}
	for(int x=0;x<=r-l;x++){
		if(sy[x]!=1){
			dp[x]=(dp[x]*(n+1))%MOD;
		}
		ans=(ans+dp[x]%MOD)%MOD;
	}
	cout<<ans<<endl;
	return 0;
}

再见 Min26 筛

见洛谷，P1835