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

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

程序：alternative.cpp。它与因数计数并列，具有 \(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\) 时只需枚举一个输入值的因数。本方案不依赖抽样概率，但可能做更多整除检查。两方案实测结果见评测说明。