京东后端笔试：桶模拟题与四因数统计

《面试题目》

1. 试剂题（桶与石头）：输入 n 个桶、m 种石头、k 次操作。操作 1 输入 idx、x、k，表示往 idx 号桶里放 k 次 x 这种石头；操作 2 输入 idx、k，查询 idx 号桶第 k 个位置的石头种类
2. 输入一个 n，再输入 n 个数，统计满足 i < j 且 ai × aj 恰好有四个因数的数对有多少个
3. AI Coding：分步骤实现得分 8700，后面怎么改都没用；重开一次性生成为 8802，之后通用样例一直不过，AI 反复排查也找不出错

《参考解析》

桶与石头：不要真的把石头存下来

关键观察是操作 1 的语义相当于往桶尾部追加一段连续区间。所以每个桶只需要维护一个列表 [(种类, 该段结束的累计位置)]，追加时把「种类 x」和新的累计总数压进去，位置用 long long 累计（总数可能超出 int）。查询第 k 个位置时，在列表里用 upper_bound 找第一个累计结束位置不小于 k 的段，对应的种类就是答案。单次追加 O(1)、查询 O(log 段数)，空间只与操作次数有关。

原帖作者用 map 存每颗石头导致内存超限，又想用「(种类, 数量)」的 pair 但不知道怎么遍历——问题就出在把「区间」当成了「逐颗记录」。这类区间追加加单点查询的题，标准解法就是前缀和加二分（或者离线处理、树状数组），不要展开元素。

四因数：先把判据想清楚

正整数 x 的因数个数由质因数分解决定：若 x = ∏ pᵢ^eᵢ，则因数个数为 ∏(eᵢ + 1)。要它正好等于 4，只有两种质因数形态：单个素数的三次方 p³，或两个不同素数的一次方乘积 p × q。所以题目等价于判断 ai × aj 的质因数签名是 {3} 还是 {1,1}。

做法是先用线性筛或最小质因子筛（范围到数值上界）预处理，把每个数分解成质因数签名，再配对计数，而不是真的去算乘积——乘积可能到 10^18 级别，直接分解乘积既慢又容易溢出。配对时按签名分类：

• 签名 {}（也就是 1）配 {3} 或 {1,1}；
• 签名 {p} 配 {p²}（同一个素数）或 {q}（不同的素数）；
• 签名 {p²} 配 {p}；
• 签名 {p³} 或 {p,q} 配 {}；
• 其余签名（指数和超过 3、或含平方以上的多素数组合）无论配什么都得不到 4 个因数。

按从左到右插入哈希表（key 是签名）并查询互补签名的个数，就能在 O(n log V) 内统计完。注意「凑成 p×q 要求两个素数不同」这个条件，同素数的一次方相乘得到的是 p²，只有三个因数。

原帖作者只拿到 25% 并超时，说明他用的是双重循环加试除判断，正确性可能没问题，但复杂度 O(n²√V) 必然过不了大数据点。这类题的通用套路就是「先做数论化简，再上哈希或筛法」。

AI Coding 卡住怎么办

作者的经历很有代表性：让 AI 分步骤做得到 8700，之后无论怎么改都上不去；重开一次性生成到 8802，通用样例一直不过，AI 只是一遍遍排查却找不到问题。可操作的止损办法：一是把失败的用例钉住，把「输入、期望输出、实际输出」三样一起贴给它，让它针对最小复现用例推理，而不是泛泛地「再检查一遍」；二是让模型先写一份对问题的理解和不变量，确认理解一致再改代码，很多死循环改不动是因为双方的模型从头就错了；三是果断换策略（重写一版暴力但正确的版本，或者自己动手改），不要在同一个上下文里反复缝补；四是限制它每次只改一个函数，便于定位是哪次修改引入的问题。时间有限时，先把能确定的分拿稳。