自动搬运

查看原文

来自洛谷，原作者为

	yihang2011 还有诗和远方的田野

搬运于2025-08-24 23:13:54，当前版本为作者最后更新于2025-04-19 19:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：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 同志的帮助，欢迎去关注他。