# 猜公因子：完整覆盖的候选检查

出题人解法：从输入项枚举候选因数，再逐项检查整除个数。Codex（GPT-6）：把停止条件明确为完整覆盖 $n-m+1$ 个位置，补充确定性证明；不使用有限抽样作为正确性依据。

程序：[alternative.cpp](alternative.cpp)。它与[因数计数](solution.zh.md)并列，具有 $O(n)$ 的空间优势，支持完整数据。

## 算法

$m=0$ 时输出 $k$ . 否则检查前 $h=n-m+1$ 个位置。对每个位置试除枚举全部不超过 $k$ 的因数。只验证严格大于当前答案的候选 $d$ ：扫描所有输入，计数能被 $d$ 整除的项；达到 $m$ 项即可更新答案，若当前计数加剩余项数仍小于 $m$ 就提前结束。答案达到 $k$ 时可以结束整个搜索。

本程序允许不同位置产生相同候选，再次扫描不会影响正确性；不维护候选集合，避免为去重增加与因数数量相关的空间。

## 正确性

设最优答案为 $x$ ，任选 $m$ 个被它整除的位置。若它们与已检查的 $h$ 个位置完全不相交，总共就有 $m+h=n+1$ 个不同位置，矛盾。因此至少一个被检查位置可被 $x$ 整除，其因数枚举会产生 $x$ .

候选检查的计数条件与题意等价，所以更新的答案始终合法。最优答案必被产生；若当时被跳过，说明当前答案已不小于它，由合法性可知已经等于它。提前失败与成功都由计数界保证正确；到达 $k$ 后不存在更大的合法值。

## 复杂度

令 $U$ 为最大输入值，$H$ 为前 $h$ 个位置不超过 $k$ 的因数数量之和（按位置计重）。试除时间为 $O(h\min(\sqrt U,k))$ ，最坏验证时间为 $O(nH)$ ，存储输入占 $O(n)$ 空间。重复候选和提前终止会影响实测耗时，但不能删去最坏时间界中的 $nH$ 项。

当 $m$ 接近 $n$ 时，$h$ 很小；例如 $m=n$ 时只需枚举一个输入值的因数。本方案不依赖抽样概率，但可能做更多整除检查。两方案实测结果见[评测说明](../../../docs/评测环境与性能.md)。