题解 [蓝桥杯 2022 国 A] 选素数

传送门

Solution

设第一次操作的结果为 $x$，选定的素数为 $p_1$。第二次操作的结果为 $y$，选定的素数为 $p_2$。由题意可得

$x-p_1+1\le y-p_2<x\le y$

题目给出的是 $y$，所求为 $x-p_1+1$ 的最小值。要使 $x$ 最小，则要使 $y-p_2$ 最小。因此找出 $y$ 的最大质因数。再枚举 $p_1$，求出符合上文不等式的最小合法 $x$，可找出答案。

Code

#include <bits/stdc++.h>
#define N 1000010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int n, pri[N], cnt, ans = 1e9, a, b, c, d, ida;
bool isp[N], flg;

void prime()
{
	for (int i = 2; i <= 1e6; i++) {
		if (!isp[i]) 
			pri[++cnt] = i;
		for (int j = 1; pri[j] * i <= 1e6; j++) {
			isp[pri[j] * i] = 1;
			if (i % pri[j] == 0) break;
		}
	}
}

int main()
{
	read(n);
	prime();
	for (int i = 1; pri[i] < n; i++)
		if (n % pri[i] == 0)
			a = pri[i];
	if (!a) {
		printf("-1");
		return 0;
	}
	b = n - a;
	for (int i = 1; pri[i] * 2 <= n; i++)
		if ((b / pri[i] + 1) * pri[i] <= n)
			ans = min(ans, (b / pri[i]) * pri[i] + 1);
	if (ans == 1e9) printf("-1");
	else printf("%d", ans);
	return 0;
}