跳转至

异星工厂:测试电路板——安全的直接求值

沿用配套讲解中“先排除过大或非正输入,再计算谓词”的方法。Codex(GPT-6)整理为精确整数实现,程序:alternative.cpp。与区间化简相比,它保留了三个谓词的求值结构,是备用方案。

先证明一个安全范围

当 \(x\le0\) 时,\(p(x)\) 为假,直接拒绝。对正整数,\(15^3=3375>3000\) ,所以 \(x\ge15\) 时,\(q(x)\) 必为假,也直接拒绝。

只有 \(1\le x\le14\) 才继续。此时平方至多 \(196\) ,立方至多 \(2744\) ,可以安全地用 64 位整数计算,然后逐项检查

\[ x^3<3000\land x^2\ge10\land(x^2>2000\lor x^2<700) \]

正确性与复杂度

被提前排除的数各有一个必要谓词为假,不会误删合法答案。剩余数全部进行准确的原条件判断,故结果与 \(P(x)\) 一致。

输入类型仍用有符号 64 位整数;范围检查必须发生在任何乘法之前。每项 \(O(1)\) 时间,整体 \(O(T+1)\) 时间、\(O(1)\) 额外空间。相比只判断区间,直接求值多做常数次运算,但更接近谓词定义。计时见主解。