# 异星工厂：测试电路板

## 解法与署名

首选出题人讲解中的精确区间化简，程序为 [std.cpp](std.cpp)。Codex（GPT-6）整理 C++17 实现与大整数输入的边界验证。区间结论已经在出题人的程序断言和讲解中给出。

另保留[安全的直接谓词求值](solution-alternative.zh.md)，程序为 [alternative.cpp](alternative.cpp)。这是按原条件逐项判断的备用实现，先缩小数值范围，再计算整数乘积。

## 化简条件

先由 $p(x)$ 得到 $x>0$ .在正整数上，平方和立方都严格递增。

因为 $3^2=9<10\le4^2=16$ ，条件 $x^2\ge10$ 等价于 $x\ge4$ .

因为 $14^3=2744<3000<3375=15^3$ ，条件 $x^3<3000$ 等价于 $x\le14$ .

二者合起来给出 $4\le x\le14$ .在这个区间内，$16\le x^2\le196<700$ ，所以 $h(x)$ 一定为真。

因此

$$P(x)\iff4\le x\le14$$

## 正确性与实现

满足全部谓词的数由前两个谓词必落在上述区间内；区间内的每个数又同时满足三个谓词。必要性和充分性都成立，直接比较两个端点即可。

使用有符号 64 位整数读入 $x$ .判断不进行平方、立方或取绝对值，因此对 $|x|\le10^{18}$ 全范围都安全，无需浮点误差阈值。

每次判断为 $O(1)$ 时间。含读入和空测试文件在内，总时间为 $O(T+1)$ ，额外空间为 $O(1)$ .

## 验证与使用

固定种子的十份正式输入配方见 `tests/plan.json` .先自行编译程序，再运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 仅生成输入；`--case 01` 选择指定用例。小规模独立验证见 [check_r16.py](../../../tools/check_r16.py)，范围校验见 [validate_r16.py](../../../tools/validate_r16.py)。五轮时间、内存、输入和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。环境与校准方法见[评测说明](../../../docs/评测环境与性能.md)。

## 实测结果

Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 -O2。两份程序在相同十份正式输入上交替运行五轮。时间取每个用例中位数的最大值，包含启动与输入输出；峰值工作集独立测量，包含运行时开销。

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 0.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [区间化简](std.cpp) | 0.027496 | 5.32 | 已测输入通过 |
| [安全直接求值](alternative.cpp) | 0.028904 | 5.32 | 已测输入通过 |

时限由标程最慢中位数乘以 2，向上取整到 0.5 秒得到。原始轮次、输入、源码和程序哈希见[测量记录](../../../docs/benchmark-R16.json)。其他评测机需重新校准；这些测量只描述随附实现及已测输入。