P3172 [CQOI2015]選數 [莫比烏斯反演+杜教篩]

傳送門

然後就是整除分塊+杜教篩

#include<bits/stdc++.h>
#define N 5000050
#define Mod 1000000007
#define LL long long
using namespace std;
int n,k,L,R;
int prim[N], isp[N], tot, mu[N];
map<int,int> Mu;
LL power(LL a,int b){
	LL ans = 1;
	for(;b;b>>=1){
		if(b&1) ans = (ans*a) % Mod;
		a = (a*a) % Mod;
	} return ans;
}
void prework(){
	mu[1] = 1;
	for(int i=2;i<=N-50;i++){
		if(!isp[i]) prim[++tot] = i, mu[i] = -1;
		for(int j=1;j<=tot;j++){
			if(prim[j] * i > N - 50) break;
			isp[prim[j] * i] = 1;
			if(i % prim[j] == 0) break;
			mu[prim[j] * i] = -mu[i];
		} 
	}
	for(int i=2;i<=N-50;i++) mu[i] += mu[i-1];
}
int getf(int x){
	if(x<=N-50) return mu[x];
	if(Mu[x]) return Mu[x];
	int ans = 1;
	for(int l=2,r;l<=x;l=r+1){
		int val = x/l; r = x/val;
		ans -= (r-l+1) * getf(val) % Mod;
		ans = (ans % Mod + Mod) % Mod;
	} return Mu[x] = ans;
}
int main(){
	prework();
	scanf("%d%d%d%d",&n,&k,&L,&R);
	L--; L/=k, R/=k;
	LL ans = 0;
	for(int l=1,r; l<=R; l=r+1){
		int v1 = L/l, v2 = R/l;
		if(v1 == 0) r = R/v2;
		else r = min(L/v1, R/v2);
		ans += (LL)(getf(r) - getf(l-1)) * power(v2-v1, n) % Mod;
		ans = (ans % Mod + Mod) % Mod;
	} printf("%lld",ans); return 0; 
}