# 猜公因子：因数出现次数

出题人解法：从选定输入位置枚举因数，并逐个检查候选是否整除足够多的项。Codex（GPT-6）：给出确定性因数计数实现、完整覆盖的停止条件、抽样局限分析及验证。试除、排序和计数均为已有基础方法。

## 首选：完整枚举并计数

当 $m=0$ 时直接输出 $k$ . 以下考虑 $m>0$ .

对每个 $a_i$ ，枚举 $1\le d\le\min(\lfloor\sqrt{a_i}\rfloor,k)$ . 若 $d\mid a_i$ ，把 $d$ 加入数组，并在 $a_i/d\le k$ 且 $a_i/d\ne d$ 时也加入其配对因数。平方根因数只计一次。对因数数组排序，连续相同值的数量就是被该值整除的输入项数；取出现次数至少为 $m$ 的最大值。

每个下标都要单独枚举，不能去重相同的输入值。循环条件写成 `d <= a / d` ，避免平方比较的溢出。

## 正确性

每个合法候选 $x$ 必须整除至少一个输入值，因数成对枚举会将它从每个可整除的下标恰好加入一次。因此排序后的计数等于 $\#\{i:x\mid a_i\}$ . 该值至少为 $m$ 当且仅当可以选出题目要求的 $m$ 个下标。遍历所有这些因数并取最大值，正好得到答案。$m>0$ 时 $1$ 总是可行；$m=0$ 时空集不施加限制，最大答案就是 $k$ .

## 复杂度

令 $U=\max_i a_i$ ，$D$ 为所有不超过 $k$ 的因数按下标计重后的总数。非空情况下试除花费 $O(n\min(\sqrt U,k))$ 时间；排序计数为 $O(D\log(D+1))$ ，空间为 $O(D+1)$ . 因数成对出现，故 $D\le2n\lfloor\sqrt U\rfloor$ ；实际 $D$ 由输入的因数个数决定。$m=0$ 时程序读完输入后输出，时间 $O(n+1)$ ，额外空间 $O(1)$ .

本题 $U\le10^9$ 时，单个数的因数个数至多为 $1344$ ，可由 $735134400$ 取到，因此 $D\le1344000$ . 这个界可通过[指数模式枚举程序](../../../tools/check_r17_divisor_bound.py)复核：固定一组素因子指数时，将较大的指数分配给较小的素数，可使数值最小而保持因数个数不变；所以只需枚举从最小素数开始、指数非递增且乘积不超过上界的模式。程序穷尽这类模式，取 $\prod_j(e_j+1)$ 的最大值。正式压力数据包含这一取到上界的数。

## 出题人思路与确定性覆盖

出题人思路只枚举部分输入位置的因数，然后对每个候选扫描全部输入验证。若检查任意 $h=n-m+1$ 个不同位置，则任意 $m$ 个位置都至少与它们相交，所以一定包含最优答案的因数来源。完整证明与程序见[候选检查法](solution-alternative.zh.md)和 [alternative.cpp](alternative.cpp)。

两方案并列：候选检查法额外空间为 $O(n)$ ，无需保存大量因数；首选计数法避免对每个候选反复扫描所有输入，其时间界没有候选验证的额外 $n$ 因子。计数法需要更多空间，不能仅因候选法在某组输入更慢就忽略其空间优势。两份确定性程序均通过当前完整数据。

## 有限抽样的局限

只随机检查固定数量的位置不能保证答案。若最优答案整除 $q$ 项，从 $n$ 项中均匀无放回抽取 $t$ 项，漏掉所有这些位置的概率为

$$\frac{\binom{n-q}{t}}{\binom nt}$$

当 $t>n-q$ 时该概率为零，否则可能为正。例如 $n=1000,m=200,k=2$ ，其中 $800$ 项为 $1$ 、$200$ 项为 $2$ ；抽到的 $50$ 项若全为 $1$ ，就会错误地输出 $1$ 而不是 $2$ . 所以固定 $50$ 次的版本不能作为保证正确的标程。

也不能直接把单次命中概率下界写成 $1/5$ ，因为约束是 $m\ge\lfloor n/5\rfloor$ ，例如 $n=9,m=1$ 时比例仅为 $1/9$ . 无放回抽样与有放回抽样的概率公式也应区别。确定性覆盖方案不依赖这些概率近似。

配方见 [plan.json](tests/plan.json)，测量见[评测说明](../../../docs/评测环境与性能.md)。验证含空集、重复值、完全平方数、上限截断及最优因数集中在输入后部的情况。