题解

思路

若 $X_i$ 与 $Y$ 不互质，则它们至少共享一个质因子。

做法

由于所有 $X_i\le50$，可能有用的质数只有 $2,3,5,\ldots,47$ 共 $15$ 个；最优答案中每个质因子也只需出现一次，因为提高指数不会覆盖新的 $X_i$，只会使 $Y$ 变大。因此枚举这 $15$ 个质数的所有非空子集，计算子集内质数的乘积，并检查它是否与每个 $X_i$ 的最大公约数都大于 $1$，在所有合法乘积中取最小值即可。

复杂度

质数子集共有 $2^{15}$ 个，每个子集检查 $N$ 个数，求最大公约数只需对不超过 $50$ 的数进行对数级运算，所以总时间复杂度为 $O(N2^{15}\log 50)$，空间复杂度为 $O(N)$；全部候选质数之积不超过 64 位有符号整数范围。