BZOJ 3930 【CQOI2015】 选数

题目链接：选数

　　这种SB题我都Wa飞了，彻底没救系列～

　　首先，我们可以发现1，如果我们选了两个不同的数，那么它们的(gcd)不会超过(r-l+1)。于是，我们可以设一个(f_i)表示任取(n)个数，它们的(gcd)为(ik)的方案数，最后我们要的答案就是(f_1)。我们考虑容斥一下，在求(f_i)的时候，先把([l,r])中是(ik)倍数的数全部拿出来，然后任意选(n)个，这样选出来的数他们的(gcd)一定是(ik)的倍数。于是，我们只需减去(f_{2i}，f_{3i}，dots，f_{lfloor frac{r-l+1}{i} floor i})即可。

　　这样的话，有可能还有些数(gcd)是(ik)的倍数我们却没统计到。由于这些未统计的(gcd)肯定比(r-l+1)大，那么肯定是选了(n)个相同的数，于是这一部分就可以直接算了。

　　下面贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
#define mod 1000000007

using namespace std;
typedef long long llg;

int n,k,l,r;
llg f[maxn];

void gi(llg &x){if(x>=mod) x%=mod;}
llg mi(llg a,int b){
	llg s=1;
	while(b){
		if(b&1) s=s*a,gi(s);
		a=a*a,gi(a); b>>=1;
	}
	return s;
}

int main(){
	File("a");
	scanf("%d %d %d %d",&n,&k,&l,&r);
	int rr=min(r/k,r-l+1);
	for(int i=rr,x,y=rr*k,z;i;i--,y-=k){
		x=(r/y)-(l/y); if(l%y==0) x++; z=(y>=l);
		for(int j=i<<1;j<=rr;j+=i) f[i]-=f[j],(f[i]+=mod)%=mod,z+=(j*k>=l);
		f[i]+=mi(x,n)-x+z; (f[i]+=mod)%=mod;
	}
	printf("%lld",(f[1]+mod)%mod);
	return 0;
}