题解

关键注意力

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

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

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

化为

十分显然。

做法：区间筛质因数

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;
}