记录编号	159171	评测结果	AAAAAAAAAA
题目名称	[CQOI 2015] 选数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2015-04-19 22:29:41	内存使用	0.79 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZE=100010;
LL realmod(LL x){
	x%=MOD;
	if(x<0) x+=MOD;
	return x;
}
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
int miu[SIZE];
void sieve(void){//筛法实力求miu
	static bool flag[SIZE]={0};
	memset(flag,0,sizeof(flag));
	for(int i=0;i<SIZE;i++) miu[i]=1;
	for(int i=2;i<SIZE;i++){
		if(!flag[i]){//i是素数
			miu[i]=-1;
			for(int j=2;j*i<SIZE;j++){
				flag[j*i]=true;
				if(j%i==0) miu[j*i]=0;
				else miu[j*i]*=-1;
			}
		}
	}
}
int N,K,L,H;
int cnt(int l,int r,int d){//[l,r]内是d的倍数的有多少个
	return r/d-(l-1)/d;
}
LL calc(int L,int H,int d){//在[L,H]内选N个数(不全相等)使其gcd是d的倍数
	LL t=cnt(L,H,d);
	return realmod(quickpow(t,N)-t);
}
void work(void){
	if(K>H-L){//这时候这N个数必须全都一样
		if(L<=K&&K<=H) printf("1\n");
		else printf("0\n");
		return;
	}
	L=(L-1)/K+1;
	H=H/K;
	//现在问题变成了:从[L,H]内取N个数使其gcd为1
	LL ans=0;
	if(L<=1) ans=1;//全相等的只有一种
	for(int d=1;d<=H-L;d++){
		ans+=calc(L,H,d)*miu[d];
		ans=realmod(ans);
	}
	printf("%lld\n",ans);
}
int main(){
	freopen("cqoi15_number.in","r",stdin);
	freopen("cqoi15_number.out","w",stdout);
	sieve();
	scanf("%d%d%d%d",&N,&K,&L,&H);
	work();
	return 0;
}