自动搬运

查看原文

来自洛谷，原作者为

	yszkddzyh 回首向来萧瑟处，归去，也无风雨也无晴

搬运于2025-08-24 22:44:32，当前版本为作者最后更新于2023-02-05 12:15:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道 hack 题。具体的规则不多说了，直接看解法。

首先是第一个问题，注意到给出的代码中有这样一句话：

cin >> x;
if(x % 2 == 1) ++ans;

而题目中给出：$-2\times10^9\le a_i\le2\times10^9$，我们发现 $a_i$ 可能为负，而对负数取模是会出错的。比如我们计算 (-3)%2，程序得出的结果是 $-1$，而 $-1$ 肯定是不等于 $1$ 的，所以上面的程序判断负奇数时会出错，因此我们只需要构造一个包含负奇数的输入即可，我提交的是这样的：

4
-1 -2 -3 -4

接下来看第二个问题：判断质数。发现程序中有这样一句代码：

for(int i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
}

问题在哪呢？发现代码是用 int 来存 $i$ 的值的，而这样的话当 $i\times i$ 的值大于 $2^{31}-1$ 时就会溢出导致程序错误，而题目的数据范围是 $p\le10^{12}$，所以我们只需要构造出一个大质数使 $i$ 溢出即可。打表发现小于 $10^{12}$ 的最大质数是 $999999999989$，因此输出这个数即可 AC。

最后看第三个问题，发现给出的代码用了二分。一时看不懂？没关系，出错的地方很简单。我们发现题目给出的程序中有这样一段：

int L = 1, R = 2000000000, ans;
while(L <= R) {
    int mid = (L + R) / 2;
    if(check(mid)) ans = mid, L = mid + 1;
    else R = mid - 1;
}

问题在哪呢？它用 int 存变量 $L,R$ 和 $mid$，发现数据范围是：$1\le a_i\le2\times10^9$，而计算 $mid$ 时程序将 $L$ 和 $R$ 直接相加，int 的上限是 $2147483647$，所以当 $L$ 和 $R$ 都很大时，计算 $mid$ 的过程就会溢出，所以我们需要构造一组能爆 int 的数据，我给出的是：

2
1999999999 2000000000

这样就能全部 AC 了，下面给出完整代码：

#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "4\n-1 -2 -3 -4" <<endl;
  } else if (taskId == 2) {
    cout << "999999999989" << endl;
  } else if (taskId == 3) {
    cout << "2\n1999999999 2000000000" << endl;
  } else { // 这个 else 不会被执行
    cout << "QiHai Nanami" << endl;
  }
}

2023.2.6 感谢 @Lyrically 指出一个重大错误。