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

· · 题解

[语言月赛 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;