题目翻译

输入一个正整数 $a(2\leq a\leq 3500)$,输出三个数 $h,w,r$,满足 $\dfrac1h+\dfrac1w+\dfrac1r=\dfrac4a$,输出任意一种符合的答案。

保证存在一组 $h,w,r\leq 3500$ 的合法解,但是你不需要一定输出类似的方案,输出中含有 $\geq 3500$ 的方案也是合法的。

题目思路

大家都会数学,就我不会,那就来一个不太寻常的大炮打蚊子的做法。

$\mathcal O(V^3)$ 的做法显然不能接受,我们可以枚举两维,$h$ 和 $w$,然后硬算出 $r$。

如何算出 $r$?

前置知识:简洁的取模还原分数方法

我们把 $\dfrac4a,\dfrac1h,\dfrac1w$ 全都取模变成一个整数,如何转换参考 P2613 【模板】有理数取余

设得到的三个整数为 $n,P,Q$,得到 $\dfrac1r$ 应该是 $m=n-P-Q$。然后我们将 $m$ 还原成分数,判断是否为埃及分数以及最后是否满足 $\dfrac1h+\dfrac1w+\dfrac1r=\dfrac4a$ 即可。

丑陋代码

AT submission 46467770

最后修改:2023 年 11 月 07 日
v我50吃疯狂星期四