题解 P6068 【[MdOI2020] GCD? GCD!】

FCBM71 · 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}) 的复杂度内解决