bzoj 3930 选数

Posted on | Edited on | Views:

$\gcd$ 的性质.

首先可以转化为在 $[\lceil \frac L k\rceil,\lfloor \frac R k\rfloor]$ 中取出 $n$ 个数,满足它们的 $\gcd$ 为 $1$ .

接下来的 $L,R$ 都是转化后的.

若取的 $n$ 个数不完全相同,那么它们的 $\gcd$ 一定会 $\le R-L$ .

计算出 $f(i)$ 表示取出 $n$ 个数,它们的 $\gcd$ 是 $i$ 的倍数的方案数,这个 $i$ 只用枚举到 $R-L$ .

再从大到小将 $f(2i),f(3i)\dots$ 减掉,得到的 $f(i)$ 就表示 $\gcd$ 恰好是 $i$ 的方案数了.

时间复杂度 $O((R-L+1)\cdot \log (R-L+1))$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=1e5+10;
int n,k,l,r;
int f[MAXN];
int main()
{
	n=read(),k=read(),l=read(),r=read();
	l+=k-1,l/=k,r/=k;
	for(int i=1;i<=r-l;++i)
	{
		int x=r/i-(l-1)/i;
		f[i]=add(fpow(x,n),P-x);
	}
	for(int i=r-l;i>=1;--i)
	{
		for(int j=2*i;j<=r-l;j+=i)
			f[i]=add(f[i],P-f[j]);
	}
	if(l==1)
		f[1]=add(f[1],1);
	cout<<f[1]<<endl;
	return 0;
}