题解：P10426 [蓝桥杯 2024 省 B] 宝石组合
ダ月
·
·
题解
我们不妨对 H_a,H_b,H_c 质因数分解，H_a=\prod p_i^{a_i}，H_b=\prod p_i^{b_i}，H_c=\prod p_i^{c_i}。
那么有以下推导：
\begin{aligned}
H_aH_bH_c\dfrac{\operatorname{lcm}(H_a,H_b,H_c)}{\operatorname{lcm}(H_a,H_b)\operatorname{lcm}(H_a,H_c)\operatorname{lcm}(H_b,H_c)}&=\prod p_i^{a_i+b_i+c_i+\max(a_i,b_i,c_i)-\max(a_i,b_i)-\max(a_i,c_i)-\max(b_i,c_i)}
\end{aligned}
不妨令 a_i\le b_i\le c_i，那么 a_i=\min(a_i,b_i,c_i)，因此：
\begin{aligned}
\prod p_i^{a_i+b_i+c_i+\max(a_i,b_i,c_i)-\max(a_i,b_i)-\max(a_i,c_i)-\max(b_i,c_i)}&=\prod p_i^{a_i+b_i+c_i+c_i-b_i-c_i-c_i}\\&=\prod p_i^{a_i}\\&=\gcd(H_a,H_b,H_c)
\end{aligned}
因此，我们只需要找到三个数，满足 \gcd 最大即可。
然后随便预处理一下每个数的因子，随便做一下就 O(n\sqrt n) 了。
代码就不给了。