151 lines
7.2 KiB
Markdown
151 lines
7.2 KiB
Markdown
##[$AcWing$ $196$. 质数距离](https://www.acwing.com/problem/content/198/)
|
||
|
||
### 一、题目描述
|
||
给定两个整数 $L$ 和 $U$，你需要在闭区间 $[L,U]$ 内找到距离最接近的两个相邻质数 $C_1$ 和 $C_2$（即 $C_2−C_1$ 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。
|
||
|
||
同时，你还需要找到距离最远的两个相邻质数 $D_1$ 和 $D_2$（即 $D_1−D_2$ 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。
|
||
|
||
#### 输入格式
|
||
每行输入两个整数 $L$ 和 $U$，其中 $L$ 和 $U$ 的差值不会超过 $10^6$。
|
||
|
||
#### 输出格式
|
||
对于每个 $L$ 和 $U$，输出一个结果，结果占一行。
|
||
|
||
结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）
|
||
|
||
如果 $L$ 和 $U$ 之间不存在质数对，则输出 `There are no adjacent primes.。`
|
||
|
||
|
||
#### 数据范围
|
||
$1≤L<U≤2^{31}−1$
|
||
|
||
#### 输入样例
|
||
```cpp {.line-numbers}
|
||
2 17
|
||
14 17
|
||
```
|
||
|
||
#### 输出样例
|
||
```cpp {.line-numbers}
|
||
2,3 are closest, 7,11 are most distant.
|
||
There are no adjacent primes.
|
||
```
|
||
|
||
### 二、二次筛法
|
||
这里的区间范围给定的最大值是$2^{31} - 1$,而用线性筛法求的是$[1,n]$中的所有质数，因此直接用线性筛法求肯定会直接挂掉，因此需要通过挖掘某些性质，才能完成。
|
||
|
||
#### 1.挖掘性质
|
||
* **性质**$1$
|
||
若一个数$n$是一个合数，必然存在$2$个因子$d$,$\large \frac{n}{d}$，假设$d <=\frac{n}{d}$，则$d <= \sqrt{n}$，因此必然存在一个小于等于 $\sqrt{n}$的因子
|
||
|
||
* **性质$2$**
|
||
若$x∈[L,R]$,且$x$是合数，则一定存在$P <= \sqrt{2^{31}-1} (< 50000)$，使得$P$能整除$x$，其中$P < x$。
|
||
$\sqrt{2147483647}=46340$,这个值是小于$50000$的，所以，$yxc$老师一般喜欢使用直接写上上限值$50000$,就是因为这个数字够用，而且够大，好记。
|
||
|
||
#### 2.实现步骤
|
||
* 找出$1 \sim \sqrt{2^{31}-1}$ $(< 50000)$中的所有质因子
|
||
* 对于$1 \sim 50000$ 中每个质数$P$，将$[L,R]$中所有$P$的倍数筛掉(至少$2$倍,$1$倍的就是自己，是质数不是合数)
|
||
找到大于等于$L$的最小的$P$的倍数$P_0$，找下一个倍数时只需要$+= P$即可
|
||
|
||
#### 3.引理
|
||
在**寻找大于$L$的第一个$P$的倍数**时，采用了下面的引理：
|
||
引理(分数的上取整转换下取整)
|
||
<center><img src='https://cdn.acwing.com/media/article/image/2020/04/15/7416_1754401c7f-2020-04-15_182406.jpg'></center>
|
||
|
||
|
||
#### 4.细节
|
||
$Q$: 每个质数是$2\sim 50000$中的数，为啥 `LL p = primes[i]`; 这里的`p`的`LL`啊， `int` 不就够了吗？
|
||
$A$: `LL p = primes[i]`，这里`p`用`LL`是因为如果`p`也是用`int`类型，本身`l`也是用`int`类型，如果`l`取得足够大，下面的`l + p - 1`会有可能直接爆`int` <font color='red'><b>变成负数</b></font>
|
||
|
||
$Q$: `for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)` 这里的 `j` 是小于等于 `r` 的，而 `r` 的取值范围是小于$2 ^ {31}$，也是在`int` 范围内啊， 这里为啥用`LL`啊？
|
||
$A$: 这里的 `j` 是小于等于 `r` 的，而 `r` 的取值范围是小于$2 ^ {31}$,这里确实是这样，可是这个循环跳出的条件是`j <= r`，也就是说如果`r`是最大的`int`，那么当`j += p`，要超过最大的`int`的时候需要比它还大才能跳出循环，因此直接爆`int`变成负数，然后`j <= r`依然成立，会一直死循环下去。其实本质上这个问题与问题$1$是一回事，<font color='red'><b>在做数论时一次要小心$LL$和$int$的加法、乘法，小心爆$int$是一条死规则，尽量多想想是不是应该用$LL$来设置变量~</b></font>
|
||
|
||
$Q$: 为什么要写上常数$50000$呢？
|
||
$A$:
|
||
* 写法$1$: `get_primes(50000)`
|
||
* 写法$2$: `get_primes(sqrt(r))`
|
||
* 写法$3$: `get_primes(sqrt(INT32_MAX))`
|
||
其实都行，但有了经验后，发现，直接写$50000$最简单粗暴效果好~
|
||
|
||
$Q$: 为什么要使用偏移量`st[j - l] = true`?
|
||
$A$: 因为数据范围太大，直接用数组进行桶计数，会超空间，需要离散化一下，就是把$1e6$范围内的数据映射到$0\sim 1e6$
|
||
|
||
$Q$:为什么`for (int i = 1; i < cl; i++) `这里要用`cl-1`呢？为什么不是`cl`呢？
|
||
$A$:$cl$个质数，下标是$[1,cl]$,因为现在枚举的是前一个质数，要保证还有后一个，所以取不到$cl$
|
||
|
||
|
||
#### 5.时间复杂度
|
||
$O(n)$
|
||
|
||
### 三、实现代码
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
// 线性筛
|
||
const int N = 1e6 + 10;
|
||
int primes[N], cnt;
|
||
bool st[N];
|
||
void get_primes(int n) {
|
||
memset(primes, 0, sizeof primes);
|
||
memset(st, 0, sizeof st);
|
||
cnt = 0;
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!st[i]) primes[cnt++] = i;
|
||
for (int j = 0; primes[j] * i <= n; j++) {
|
||
st[primes[j] * i] = true;
|
||
if (i % primes[j] == 0) break;
|
||
}
|
||
}
|
||
}
|
||
|
||
bool b[N]; // 记录区间内有哪些数是合数
|
||
int c[N], cl; // 区间内有哪些质数
|
||
int l, r; // 区间范围
|
||
|
||
int main() {
|
||
// 加快读入
|
||
ios::sync_with_stdio(false), cin.tie(0);
|
||
|
||
// 一次性筛质数
|
||
get_primes(50000);
|
||
|
||
while (cin >> l >> r) {
|
||
memset(b, 0, sizeof b); // 清除合数数组
|
||
memset(c, 0, sizeof c); // 清除质数数组
|
||
cl = 0;
|
||
|
||
// 标识质数的倍数，也就是合数有哪些
|
||
for (int i = 0; i < cnt; i++) {
|
||
LL p = primes[i];
|
||
for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p) // 枚举p的2倍以上倍数，最小要比l大，最大不能超过r
|
||
b[j - l] = true; // 采用偏移量记录剔除标识
|
||
}
|
||
|
||
// Hack data: 1 100
|
||
// 输出： 1,2 are closest, 89,97 are most distant.
|
||
// 答案： 2,3 are closest, 89,97 are most distant.
|
||
// 原因： 下面的逻辑判断b[i]是否等于0，表示i+l不是某个质数的倍数（合数），也就是是合数，但这样判断是有问题的，因为考虑边界问题
|
||
// 1通过上面的代码是无法剔除掉的，也就是说，上面的剔除的是合数，但数字除了合数，可不是只有质数，还有一个特殊的数字1，1即不是质
|
||
// 数也不是合数,这句话可不是说说而已。
|
||
for (int i = 0; i <= r - l; i++)
|
||
if (!b[i] && i + l > 1) // 如果不是合数，并且，不是1，才是质数
|
||
c[++cl] = i + l; // 区间内的质数多了一个i+l质数
|
||
|
||
if (cl < 2)
|
||
puts("There are no adjacent primes.");
|
||
else {
|
||
int mi = 1, mx = 1; // 第一只猴子就是大王
|
||
for (int i = 1; i < cl; i++) { // 范围是1~cl,而此处因为要枚举的是每个当前i与后一个的关系，所以需要枚举到cl-1
|
||
int d = c[i + 1] - c[i];
|
||
if (d < c[mi + 1] - c[mi]) mi = i;
|
||
if (d > c[mx + 1] - c[mx]) mx = i;
|
||
}
|
||
printf("%d,%d are closest, %d,%d are most distant.\n", c[mi], c[mi + 1], c[mx], c[mx + 1]);
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
```
|