bzoj3930:[CQOI2015]选数

传送门

容斥。
发现(H-L)范围很小
设(f[i])为最大公约数为(i)且选的数不全相同的方案数
考虑将(H)和(L)除以(k)，设(l=lfloor L/k floor,r=lfloor H/k floor)
那么答案就是(f[1]+[L<=k且k<=H])
考虑怎么求出(f)，首先可以处理出最大公约数是(i)的倍数且选的数不全相同的方案数，也就是((r-l)^n-(r-l))
然后枚举(i)的倍数，(f[i]=f[i]-sum_{j|i}f[j])
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10,mod=1e9+7;
int n,k,l,r,len,ans,f[maxn];
int mi(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1ll*ans*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return ans;
}
int main()
{
	read(n),read(k),read(l),read(r);
	if(l<=k&&r>=k)ans++;
	l--,l/=k,r/=k,len=r-l;
	for(rg int i=len,x,y;i;i--)
	{
		x=l/i,y=r/i;
		f[i]=(mi(y-x,n)-y+x+mod)%mod;
		for(rg int j=i+i;j<=len;j+=i)(((f[i]-=f[j]))+=mod)%=mod;
	}
	printf("%d
",ans+f[1]);
}