题解：P12235 [蓝桥杯 2023 国 Java A] 躲炮弹

· · 题解

题解：P12235 [蓝桥杯 2023 国 Java A] 躲炮弹

提示：这是一篇 C++ 题解。

类似判断质数的题，其实正解很简单，但是我唐到调了两个多小时还发帖求助来着。

思路很简单，跟筛法半点关系没有。

设计一个判断函数，然后从小到大枚举答案 ans，那么当前位置就是 n - ans 或 n + ans，判断这两个位置是否合法（能否被 [L, R] 中的数整除），合法就输出 ans，并退出。

很简单吧，来看判断函数。首先可以想到直接从 L 到 R 枚举因数，答案正确，但是超时了，两个点 TLE。

考虑根据质数判断优化，想到因数应该枚举到 \sqrt{x}，然后就 WA 了一个点。

可以发现 x 的因子 k 可能满足 \sqrt{x} < k \le R 没有考虑到，且这些 k 都可以满足 \displaystyle \frac{x}{k} < \sqrt{x}，所以在枚举因子的时候可以从 1 枚举到 \sqrt{x}，并且判断 k 是否为 x 的因子，如果是，那么在判断 k 与 \displaystyle \frac{x}{k} 是否属于 [L, R] 即可。

时间很极限，肯定是有更好的方法的，但我想不到了。

其他的没什么要注意的了，代码如下：

#include <iostream>
using namespace std;

int n, L, R, ans;

bool chk(int x) {
    for (int i = 1; i * i <= x; i++) { // i 即文中的 k
        if (x % i == 0 && (i >= L && i <= R || x / i >= L && x / i <= R)) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> L >> R;
    for (; !chk(n - ans) && !chk(n + ans); ans++);
    cout << ans << endl;
    return 0;
}

AC Record

我唐到目前一共 83 条评测记录我贡献了 60 条而且完全拉低了通过率。

由于自己唐完了而且过于蒟蒻发了求助帖，很感谢 mymmzh 同志的帮助，欢迎去关注他。