题解 [蓝桥杯 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;
}