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

这里说一个 $O(T\max(\log^3 n,n^\frac{1}{4}))$ 的优（胃）秀（疼）算法。 考虑对于一种拆分是最优的。即 $(a,b,c)=d$，$d$ 为所求，那么发现会有 $d\cdot (\frac{a}{d}+\frac{b}{d}+\frac{c}{d})=n$。发现当 $\frac{a}{d},\frac{b}{d},\frac{c}{d}$ 三者不同时，一定可以转化成其中一个数 $=d$ 的构造方式。 所以考虑质因数分解之后枚举 $\frac{n}{d}$。发现当 $\frac{n}{d}\leq 5$ 的时候，当前枚举的 $d$ 不可以让 $\frac{a}{d},\frac{b}{d},\frac{c}{d}$ 三者不同。所以判掉这些数据，剩下的取 $\rm max$ 即可。 发现现在要求的，就是从 $n$ 的所有分解里面，挑出一个最接近 $6$ 且 $\geq 6$ 的构造 $\frac{n}{d}$ 的方案。发现最多需要三个素因子才可以超过 $6\to (2,2,2)$，最少的话一个就足够了。所以考虑 $\log ^3n$ 三重循环枚举所有的质因子即可。 质因数分解完全可以 $\rm pollard-rho$。最后复杂度 $O(T\max(\log^3 n,n^\frac{1}{4}))$ 代码就不展示了，按照上述方式实现，代码应该十分 $naive$。