猜公因子：因数出现次数¶
出题人解法：从选定输入位置枚举因数，并逐个检查候选是否整除足够多的项。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\) . 这个界可通过指数模式枚举程序复核：固定一组素因子指数时，将较大的指数分配给较小的素数，可使数值最小而保持因数个数不变；所以只需枚举从最小素数开始、指数非递增且乘积不超过上界的模式。程序穷尽这类模式，取 \(\prod_j(e_j+1)\) 的最大值。正式压力数据包含这一取到上界的数。
出题人思路与确定性覆盖¶
出题人思路只枚举部分输入位置的因数，然后对每个候选扫描全部输入验证。若检查任意 \(h=n-m+1\) 个不同位置，则任意 \(m\) 个位置都至少与它们相交，所以一定包含最优答案的因数来源。完整证明与程序见候选检查法和 alternative.cpp。
两方案并列：候选检查法额外空间为 \(O(n)\) ，无需保存大量因数；首选计数法避免对每个候选反复扫描所有输入，其时间界没有候选验证的额外 \(n\) 因子。计数法需要更多空间，不能仅因候选法在某组输入更慢就忽略其空间优势。两份确定性程序均通过当前完整数据。
有限抽样的局限¶
只随机检查固定数量的位置不能保证答案。若最优答案整除 \(q\) 项，从 \(n\) 项中均匀无放回抽取 \(t\) 项，漏掉所有这些位置的概率为
当 \(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\) . 无放回抽样与有放回抽样的概率公式也应区别。确定性覆盖方案不依赖这些概率近似。