给出三个整数 $l,r,k (1 \le l \leq r \le 2\cdot10^9, 2 \le k \le 2 \cdot 10^9)$ 。
求在区间 $[l,r]$ 内满足 $k \mid i$ ， 且对于任意 $j \in [2,k-1]$ 都不满足 $k \mid i$ 的数 $i$ 的个数。
链接
Codeforces
题解
可以发现，问题可以转化为在 $[l,r]$ 中最小质因数是 $k$ 的数的个数。
现将问题差分，变成在 $[1,n]$ 以内最小质因数是 $k$ 的数的个数。
我们考虑转化问题，如果我们令 $f[i]$ 为 $i$ 的最小质因数，那么显然这个可以在线性的时间内筛出来（我们预处理一些，假设到 $\text{MAX}$ ）。
我们的问题就可以变成：
求出在 $[1,n]$ 中，$f[i] = k$ 的数的个数，明显发现，这个可以转化为在 $[1,\lfloor\frac{n}{k}\rfloor]$ 内， $f[i] \ge k$ 的数的个数。
我们可以对数据进行分治，如果我们发现：
我们可以对数据进行分治，如果我们发现：
- $\lfloor\frac{n}{k}\rfloor < \text{MAX}$，直接线性解决这个问题
- $\lfloor\frac{n}{k}\rfloor \ge \text{MAX}$，这个时候如果我们线性筛筛的比较大，剩下的 $k$ 应该会比较小。这个时候事实上我们要求的是所有 $[1,n]$ 当中有多少个数存在一个小于 $k$ 的质因数，这个东西可以容斥解决。容斥的复杂度是 $2^k$，那么我们应该让线性筛筛出来的东西尽量大即可。而且事实上我们可以加入一个剪枝，也就是一旦你现在要容斥的数已经超过了 $n$ ，就直接 break 掉。
这样的话，复杂度大约是可以过掉的。
实际上可能要调一调线性筛的 $\text{MAX}$ ，但这个题目时限比较宽松，也是可以过掉的。
代码
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000000;
int prime[MAXN],cnt;
bool vis[MAXN];
int f[MAXN];// 最小质因数
void sieve(){
memset(vis,0,sizeof(vis));
f[1] = 1;
for(int i = 2;i<MAXN;i++){
if(vis[i] == 0){
f[i] = i;
prime[++cnt] = i;
}
for(int j = 1;i*prime[j]< MAXN && j<=cnt;j++){
vis[i*prime[j]] = 1;
f[i*prime[j]] = prime[j];
if(i%prime[j] == 0)
break;
}
}
}
bool is_prime(int k){
int t = sqrt(k);
for(int i = 2;i<=t;i++){
if(k % i == 0)return 0;
}
return 1;
}
int cal1(int n,int k){
int ans = 0;
for(int i = 1;i<=n;i++){
if(i == 1 || f[i] >= k) ans++;
}
return ans;
}
int LIM = 0,lim = 0;// LIM 质数个数，lim 为 n/k
#define ll long long
ll ans = 0;
void dfs(int p,ll now,ll f){
if(now > lim) return;
if(p > LIM) {
ans += f * (lim/now);return;
}
dfs(p+1,now,f);
dfs(p+1,now*prime[p],-f);
}
int cal2(int n,int k){
LIM = 0,lim = n,ans = 0;
for(int i = 1;prime[i] < k;i++)LIM++;
dfs(1,1,1);
return int(ans);
}
int calc(int n,int k){
if(!n || !is_prime(k)) return 0;
if(n/k < MAXN) return cal1(n/k,k);
else return cal2(n/k,k);
}
int l,r,k;
int main(){
scanf("%d %d %d",&l,&r,&k);
sieve();
printf("%d\n",calc(r,k) - calc(l-1,k));
return 0;
}
|
