E. Secret Box 详细题解

题目重述

有一个大盒子 $B$，尺寸为 $x \times y \times z$（$x, y, z \le 2000$），放置在三维空间从 $(0,0,0)$ 到 $(x,y,z)$ 的区域内。我们要选择一个小盒子 $S$，其边长 $a, b, c$ 均为正整数，体积 $a \cdot b \cdot c = k$，并将其平行于坐标轴放置，所有角点坐标为整数，且完全位于 $B$ 内部（即 $0 \le a \le x$ 等）。问：在所有可能的 $(a,b,c)$ 选择中，$S$ 可以放置的位置数最大为多少？若不存在合法的 $(a,b,c)$，输出 $0$。

核心思路

• 若固定 $(a,b,c)$，则 $S$ 的左下角（最靠近原点的角点）可以在 $x$ 方向上取 $0$ 到 $x-a$ 的整数，共 $x-a+1$ 个位置；同样 $y$ 方向有 $y-b+1$ 个位置，$z$ 方向有 $z-c+1$ 个位置。因此总放置方法数为：

• 我们需要在所有满足 $a \cdot b \cdot c = k$ 的正整数三元组 $(a,b,c)$ 中，最大化上式，并输出最大值（若无合法三元组则输出 $0$）。

数据范围与特点

• $x, y, z \le 2000$，且所有测试用例的 $x, y, z$ 各自的总和不超过 $2000$，因此单次最多 $2000$。
• $k$ 可能很大（最大 $x\cdot y\cdot z \le 8\cdot 10^9$），但 $k$ 的因子个数不会很多（最坏情况下，$k \le 8\times 10^9$ 时约 $10^3$ 量级）。
• 我们可以通过枚举 $a$ 和 $b$ 的方式，但直接枚举 $a$ 从 $1$ 到 $x$，$b$ 从 $1$ 到 $y$ 会达到 $O(x \cdot y)$，最多 $4\times 10^6$，虽然可行但可优化。更高效的方法是枚举 $k$ 的所有因子作为 $a$，再枚举因子作为 $b$，这样只需枚举 $O(d(k)^2)$ 种组合，其中 $d(k)$ 是 $k$ 的因子个数，通常很小。

算法步骤

1. 读入 $x, y, z, k$。
2. 枚举 $k$ 的所有正因子，存入列表 $D$。
3. 对 $D$ 排序（便于剪枝）。
4. 初始化答案 $ans = 0$。
5. 对每个 $a \in D$，若 $a > x$ 则终止（因为 $a$ 递增，后续更大）。
   • 令 $r = k / a$（$r$ 是剩余部分）。
   • 对每个 $b \in D$，若 $b > y$ 则终止。
     • 若 $r$ 不能被 $b$ 整除，跳过。
     • 否则 $c = r / b$，若 $c \le z$，则计算：$$ways = (x - a + 1) \cdot (y - b + 1) \cdot (z - c + 1) $$并更新 $ans = \max(ans, ways)$。
6. 输出 $ans$。

正确性证明

• 任何合法的 $(a,b,c)$ 必须满足 $a \mid k$，$b \mid (k/a)$ 且 $c = k/(ab)$，因此 $a$ 和 $b$ 必须是 $k$ 的因子。枚举所有因子对即可覆盖所有可能。
• 放置位置数由公式给出，取最大值即可。
• 若没有合法的 $(a,b,c)$，则 $ans$ 保持 $0$，输出 $0$。

复杂度分析

• 预处理因子：$O(\sqrt{k})$，由于 $k$ 最大约 $8\times 10^9$，$\sqrt{k} \le 10^5$，但实际 $x,y,z\le 2000$ 限制了 $k$ 的上限，且所有测试用例的总 $x,y,z$ 很小，因此枚举所有因子在时间允许范围内。
• 枚举因子对：$O(d(k)^2)$，$d(k)$ 通常很小（如 $k= 2^{30}$ 时约 $31$，$k= 10^9$ 时最多 $1344$），因此 $d(k)^2$ 最大约 $1.8\times 10^6$，加上排序和循环剪枝，在 $t\le 2000$ 且总 $x,y,z$ 和 $\le 2000$ 的条件下可以轻松通过。

边界情况

• 当 $k=1$ 时，因子只有 $1$，那么 $a=b=c=1$，放置方法数为 $x \cdot y \cdot z$。
• 当存在 $a > x$ 或 $b > y$ 或 $c > z$ 时，该三元组不可用，直接跳过。
• 若没有任何因子对满足 $a \le x, b \le y, c \le z$，输出 $0$。

示例验证

• 样例 $1$：$x=3,y=3,z=3,k=8$。因子有 $1,2,4,8$。枚举：
  • $a=2,b=2,c=2$：位置数 $(3-2+1)^3 = 8$，最大。
  • $a=1,b=1,c=8$ 不合法（$c>3$）。答案为 $8$。
• 样例 $2$：$k=18$，因子 $1,2,3,6,9,18$。最优 $(2,3,3)$ 位置数 $(3-2+1)\cdot(3-3+1)\cdot(3-3+1)=2\cdot1\cdot1=2$，与输出一致。
• 样例 $3$：$x=5,y=1,z=1,k=1$，只有 $(1,1,1)$，位置数 $5\cdot1\cdot1=5$，正确。
• 样例 $4$：$x=2,y=2,z=2,k=7$，因子有 $1,7$，$c=7>2$ 且 $a=b=7$ 无效，答案为 $0$。

总结

本题的关键在于将几何放置问题转化为对体积 $k$ 的因子分解，并计算每个因子组合产生的放置位置数。由于 $x,y,z$ 很小，枚举因子即可高效求解。注意使用 $64$ 位整数存储乘积，避免溢出。