记录编号	409482	评测结果	AAAAAAAAAA
题目名称	[CQOI 2015] 选数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.509 s
提交时间	2017-05-27 21:21:41	内存使用	8.89 MiB

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
int n,k,l,r,u[N],p[N],cnt;
bool isp[N];
int inc(int x,int y){x+=y;return x>=mod?x-mod:x;}
int dec(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
void init(){
	u[1]=1;
	for (int i=2;i<N;i++){
		if (!isp[i]) p[++cnt]=i,u[i]=-1;
		for (int j=1;j<=cnt&&i*p[j]<N;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) u[x]=-u[i];
			else{u[x]=0;break;}
		}
		u[i]+=u[i-1];
	}
}
map<int,int> M;
int getsu(int x){
	if (x<N) return u[x];
	if (M.count(x)) return M[x];
	M[x]=1;
	for (int l=2,r;l<=x;l=r+1){
		r=x/(x/l);
		M[x]-=(r-l+1)*getsu(x/l);
	}
	return M[x];
}
int main()
{
	freopen("cqoi15_number.in","r",stdin);
	freopen("cqoi15_number.out","w",stdout);
	scanf("%d%d%d%d",&n,&k,&l,&r);
	l=(l-1)/k+1;r/=k;
	if (l>r) return puts("0"),0;
	//直接mobius反演即可
	init();
	int ans=0;
	l--;
	for (int L=1,R;L<=r;L=R+1){
		if (l/L) R=min(l/(l/L),r/(r/L));else R=r/(r/L);
		int size=r/L-l/L;
		ans=inc(ans,mul(dec(getsu(R),getsu(L-1)),power(size,n)));
	}
	/*for (int i=1;i<=r;i++){
		int L=(l-1)/i+1,R=r/i;
		int size=R-L+1;
		if (u[i]>0) ans=inc(ans,power(size,n));
		if (u[i]<0) ans=dec(ans,power(size,n));
	}*/
	printf("%d\n",ans);
	return 0;
}