P9009 牵连的世界 (Hard Version) 题解

· · 题解

这是一道 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 指出一个重大错误。