CQOI2015 选数

Description

link

给定区间 ([space l,r space ]) 和整数 (N) , (K)，求有多少种方案，使得在区间中选出的 (N) 个数的最大公约数为 (K)

Solution

怼式子的时候先两边同除(K)，把题意转换成：在区间$[lfloor frac{L}{k} floor,lfloor frac{R}{k} floor] $ 中选数，(gcd=1)

端点的细节需要注意：(l \% k==0 ightarrow l=lfloor frac{L}{k} floor+1)

然后设(f(x)) 为表示选出的数的公约数有 (x) 且选出的数不全相同的方案数

显然有(f(x)=(frac{r}{x}-frac{l}{x})^n-(frac{r}{x}-frac{l}{x}))

即考虑(x)的倍数，然后区间容斥一下，如果选的数全都一样，是不可以的

我们发现如果把 (f(x)) 减掉 (f(x) 的倍数())就是正确答案了

这里可以考虑容斥一波

最后注意一下取模

同时也可以反演之后套杜教筛解决

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=1e5+10;
	const int mod=1e9+7; 
	inline int ksm(int x,int y)
	{
		int res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod;
		return res;
	}
	int f[N],n,l,r,k;

	signed main()
	{
		n=read(); k=read(); l=read(); r=read();
		(l+=k-1)/=k; r/=k;
		if(l>r) return puts("0"),0;
		for(int i=1;i<=r-l;++i) 
		{
			int tl=(l+i-1)/i,tr=r/i;
			if(tr<tl) continue;
			f[i]=(ksm(tr-tl+1,n)-(tr-tl+1)+mod)%mod;
		}
		for(int i=r-l;i;--i)
		{
			for(int j=i*2;j<=r-l;j+=i)
			{
				f[i]=(f[i]-f[j]+mod)%mod;
			}
		} printf("%lld
",l==1?f[1]+1:f[1]);
		return 0;
	}
}
signed main(){return yspm::main();}