P9473 [yLOI2022] 西施江南

一扶苏一 · 2023-08-04 17:25:54 · 题解

Analysis

考虑唯一分解定理，对 n 个数 a_1, a_2, a_3, \dots a_n，设 a_i = \prod p_j^{c_{i,j}}。则其 \gcd = \prod p_j ^{\min\limits_i c_{i,j}}，\mathrm{lcm} = \prod p_j^{\max\limits_i c_{i,j}}。\gcd \times \mathrm{lcm} = \prod p_j^{\min\limits_i c_{i,j} + \max\limits_i c_{i,j}}。又 \prod a_i = \prod p_j^{\sum_{i= 1}^n c_{i,j}}。于是回答为是的充要条件是 \sum_{i = 1}^n c_{i,j} = \min c_{i,j} + \max c_{i,j}。易见 \max c_{i,j} 一定是左边的一项，所以需要 \min c_{i,j} 等于左边剩下的项。

讨论一下：

2. 当 n > 2 时，假设 \min c_{i,j} = k。不妨假设 \min c_{ i,j} = c_{1,j} \leq c_{2, j} \leq c_{3, j} \leq \dots \leq c_{n,j} = \max c_{i,j}。想要让这些项目的和等于 \min c_{i,j} + \max c_{i,j}，则 c_{2,j} = c_{3, j} = c_{4, j} = \dots = c_{n - 1,j} = 0。又 c_{2,j} \geq \min c_{i,j}，于是 \min c_{i,j} = 0。
   因此，此时每个质数只能作为一个数字的因子。换句话说，数字是两两互质的。

综上，当 n = 2 时，总是回答是，否则如果给定的数字两两互质，回答是，否则回答否。

子任务 1