自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:18:06，当前版本为作者最后更新于2025-03-19 17:28:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛 202503] 半个哥德巴赫猜想 题解

Source & Knowledge

本题来源于 2025 年 3 月的语言月赛，涉及复杂循环嵌套等知识。

文字题解

题目要求将 $n$ 表示为一个缪零数与一个质数的和，并统计方案数，同时找出方案中最小的差值。

定义回顾 我们首先回顾缪零数与质数的定义：

1. 缪零数：$n$ 是某个 $m^2$ 的倍数（$m \geq 2$），这隐含了 $n \geq 4$。
2. 质数：$n$ 不能被 $2\sim n-1$ 中任意一个整数整除，且 $n \neq 1$。

我们不妨首先考虑如何判断缪零数和质数。

缪零数 对于一个整数 $i$，我们可以遍历 $k = 2 \sim i - 1$，逐个判断 $i$ 是否是 $k \times k$ 的倍数。如果有任何 $k$ 满足 $i$ 是 $k \times k$ 的倍数，则 $i$ 是缪零数。

int flag = 0; // 记录 i 是否是缪零数，1 代表是，0 代表不是
for (int k = 2; k <= i - 1; k++) {
    if (i % (k * k) == 0) { // i 除以 k * k 的余数是 0，代表了 i 是 k * k 的倍数
        flag = 1;
        break;
    }
}

质数 同理，对于一个整数 $i$，我们遍历 $k = 2 \sim i - 1$，逐个判断 $i$ 是否是 $k$ 的倍数。如果有任何 $k$ 满足 $i$ 是 $k$ 的倍数，则 $i$ 不是质数。反之，则 $i$ 是质数。

int flag = 1; // 记录 i 是否是质数，1 代表是，0 代表不是
for (int k = 2; k <= i - 1; k++) {
    if (i % k == 0) {
        flag = 0;
        break;
    }
}

有了上面两部分代码，我们只需要在最外层套一个 for 循环枚举把 $n$ 分拆的方案即可。例如，我们可以枚举 $i = 4 \sim n - 2$ 并假定 $i$ 是拆出来的缪零数，那么 $j = n - i$（范围 $2 \sim n - 4$）则被假定是拆出来的质数。

for (int i = 4; i <= n - 2; ++i) {
    int j = n - i;

    // 分别判断 i, j 是否是缪零数、质数
    // 此处直接使用上面提到的代码部分即可，故省略

    ...
}

在找到每一种合法的分拆方案后，我们可以使用两个变量 $c, d$ 分别用于统计答案要求的数量和差的最小值。前者直接计数，后者使用擂台法即可。

int c = 0;
int d = 10000; // 由于 i - j 一定不会超过 n，n 一定不会超过 10000，因此这里 d = 10000 即可
for (int i = 4; i <= n - 2; ++i) {
    int j = n - i;
    // 分别判断 i, j 是否是缪零数、质数

    if (i, j 不满足条件) continue;

    c++;
    if (i < j) d = min(d, j - i);
    else d = min(d, i - j);
}
cout << c << endl << d << endl;