题解：P14684 [ICPC 2025 Yokohama R] Cutting Tofu
前言
题目传送门
思路讲解
一块 \(a\times b\times c\) 的豆腐，要用平行面切出至少 \(k\) 个尽可能大的立方体豆腐块。
立方体边长可为有理数，输出最简分数 \(p/q\)。
一次切割贯穿整个豆腐块，若以 \(a\) 维度 \(x\) 为基准维度，分成 \(n\) 段，那么边长为 \(s=\frac{a}{n}\)。
其他两个维度的切割次数为：
\[y=\left \lfloor \frac{b}{s} \right \rfloor=\left \lfloor \frac{b}{\frac{a}{n} } \right \rfloor=\left \lfloor \frac{b\times n}{a} \right \rfloor
\]
\[z=\left \lfloor \frac{c}{s} \right \rfloor=\left \lfloor \frac{c}{\frac{a}{n} } \right \rfloor=\left \lfloor \frac{c\times n}{a} \right \rfloor
\]
所以总方块数量为：
\[ans=n\times y\times z=n\times\left \lfloor \frac{b\times n}{a} \right \rfloor \times \left \lfloor \frac{c\times n}{a} \right \rfloor
\]
题目要求为 \(ans\ge k\)
- 所以我们用二分查找最小的 \(n\)。
- 得到可能成立的边长 \(len=\frac{N}{n}\)。
- 在三个维度中选择出最大的 \(len\) 作为 \(s\)。