CF#470 Div2 B. Primal Sport

Alice and Bob begin their day with a quick game. They first choose a starting number X0 ≥ 3 and try to reach one million by the process described below.

Alice goes first and then they take alternating turns. In the i-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime p < Xi - 1 and then finds the minimum Xi ≥ Xi - 1 such that p divides Xi. Note that if the selected prime p already divides Xi - 1, then the number does not change.

Eve has witnessed the state of the game after two turns. Given X2, help her determine what is the smallest possible starting number X0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

###Input
The input contains a single integer X2 (4 ≤ X2 ≤ 106). It is guaranteed that the integer X2 is composite, that is, is not prime.

###Output
Output a single integer — the minimum possible X0.

##Examples
###input
14
###output
6
###input
20
###output
15
###input
8192
###output
8191

In the first test, the smallest possible starting number is X0 = 6. One possible course of the game is as follows:

- Alice picks prime 5 and announces X1 = 10
Bob picks prime 7 and announces X2 = 14.

In the second case, let X0 = 15.

- Alice picks prime 2 and announces X1 = 16
Bob picks prime 5 and announces X2 = 20.

---------------

####先对一次操作考虑：

- 假设在比A小的质数中选择质数P，结果为B。那么若给定B，我们可以知道$A \in [B - p(B) + 1, B]$。 ($p(x)$表示x最大的质因数)。

但是对于两次来说，x1的个数是O(n)级别的。O(n$\sqrt n$)的复杂度是不足以应对1e6的数据的。

那么，我们考虑怎么优化。

先看，我们的区间最小值是$B - p(B) + 1$。
是不是看出了什么呀?

没看出来不要紧，我们化直观一点
由于$p(B)|B$，设原式等于：
$$f(B) = B \cdot (1 - \frac{1}{\frac{B}{p(B)}}) + 1$$
假设我们朴素的从$[B - p(B) + 1, B]$的左端点开始枚举，那么我们的B一定是单增的。此时对$\frac{B}{p(B)}$来看，不难发现$g(x)=\frac{B}{p(B)} \geq 2$，并且在此时$(1 - \frac{1}{\frac{B}{p(B)}})$有最大值。同时因为B单增，一旦有$g(B_0)=2$，那么对于所有大于$B_0$的$B$一定不会更优。这样我们只要在$g(B)=2$时退出循环就可以大大减小复杂度。

对复杂度进行分析：考虑到满足$g(B)=2$时，B一定是一个质数的两倍。因为1~N中质数的个数为$\frac{N}{logN}$，那么N以内质数的平均密度为$\frac{N}{\frac{N}{logN}}=logN$。因此我们平均会枚举的B值为$2logN$个。每一次我们用$O(\sqrt N)$计算$p(B)$。总复杂度为$O(\sqrt N\cdot logN)$

考虑到分解质因数在质数的情况下退化成O(N)，我们可以先
15ms代码：
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5;
int pri[maxn], x2, x1, mp, mn = 0x3f3f3f3f;
bool vis[maxn];
void prime(int N) {
	for(register int i = 2; i <= N; ++i) {
		if(!vis[i]) pri[++pri[0]] = i;
		for(register int j = 1; j <= pri[0] && i * pri[j] <= N; ++j) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}

int GetMP(int x) {
	if(!vis[x]) return -0x3f3f3f3f;
	int x1 = 1, x2 = x;
	for(register int i = 2; i <= x; ++i) {
		x1 = i;
		while(x % i == 0) x /= i;
	}
	return x1;
}

int main() {
	prime(1e6);
	scanf("%d", &x2), x1 = x2 - GetMP(x2);
	for(register int i = (x1 + 1); i <= min(x1 + 1 + 1000, x2); ++i) {
		mn = min(i - GetMP(i) + 1, mn);
	}
	printf("%d", mn);
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链