题目大意
在区间$[L,R]$中选$N$个数，询问选出来的数最大公约数为$K$的方案数$\bmod\,1000000007$。
题目分析
看到这道题有没有想到莫比乌斯反演？
莫比乌斯反演应该可以做，但是对于这道题就有点卡常数了。
这道题有一种更为快速简洁巧妙的算法：
注意$R-L\le10^5$这个条件，说明我们应该往区间长度入手。
注意到一个性质：若$n$个数不全部相同，那么它们的最大公约数小于它们的极差。证明很显然：当$Max\neq Min$时，$Max-Min=gcd(Max’-Min’)>gcd$。
因此我们可以发现，在一个区间$[L,R]$中选不全部相同数，其最大公约数一定小于$R-L$。
我们将区间中的数都除以$k$，就变成统计$[\frac{L-1}{k}+1,\frac{R}{k}]$中$gcd$等于$1$的方案数。
如何计算$gcd$等于$1$的方案数呢？
我们可以使用容斥原理的动态规划计算。
设$f[i]$为$gcd$是$iK$的方案数，我们可以这样计算：
我们同样可以先堆区间除以$iK$，然后计算$gcd$等于$1$的方案数。
$f[i]=$总方案数$-gcd\neq1$的方案数$-$全部选相同数的方案数。
设当前区间为$(x,y]$（已除以$iK$），总区间长度为$len$（已除以$K$）
这里的$j$是$i$的倍数，因此算法是$O(len\log len)$的。
最后答案则为$f[1]+k$是否在区间内。
因为我们计算的是不全相同的方案数，如果$k$在区间内还可以全部选$k$。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1000000007;
LL n,k,Left,Right,f[100005],len;
bool tmp=0;
LL Quick_Pow(LL a,LL b) {
LL ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main() {
n=Get_Int();
k=Get_Int();
Left=Get_Int();
Right=Get_Int();
if(Left<=k&&k<=Right)tmp=1;
Left=(Left-1)/k;
Right/=k;
len=Right-Left;
for(int i=len; i>=1; i--) {
int x=Left/i,y=Right/i;
f[i]=((Quick_Pow(y-x,n)-y+x)%mod+mod)%mod;
for(int j=i<<1; j<=len; j+=i)f[i]=((f[i]-f[j])%mod+mod)%mod;
}
printf("%lld\n",f[1]+tmp);
return 0;
}
|
