自动搬运

查看原文

来自洛谷，原作者为

	FCBM71 AFO

搬运于2025-08-24 22:17:06，当前版本为作者最后更新于2020-02-09 18:19:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实是很简单的一道题，用不着二分再check什么的

假设这个最后的答案为 $g$
并假设 $a=A\times g$，$b=B\times g$，$c=C\times g$，令 $k=A+B+C$
那么总和 $n=(A+B+C)\times g=k\times g$

由于 $g$ 和 $k$ 都是整数，所以他们都是 $n$ 的约数。为了最大化 $g$，我们需要 $k$ 尽可能小。

因为$a,b,c$ 互不相等，所以 $A,B,C$ 也一定互不相等。因此 $k$ 也一定能表示成三个互不相等的整数的和。什么样的 $k$ 才可以呢？只要 $k\geq 6$ 就可以了。因为 $k=6$ 是恰好为 $1+2+3$，比 $6$ 更大时一定可以拆成 $1+2+(k-3)$ 的形式。

综上，本题要求的就是： 寻找一个最小的 $k$，使得 $k\geq 6$ 且 $n\%k=0$。
输出的答案应该是 $n/k$。
可以根据筛质数时的原理在 $O(\sqrt{n})$ 的复杂度内解决