题解：CF2115A Gellyfish and Flaming Peony

ax_by_c · 2025-06-21 09:45:34 · 题解

训练赛考了加强版，自己推出来了，来写一下。

首先对于这个题最后肯定是变成全局的 \gcd，那么大可直接把所有数全部除以全局 \gcd。那么出现 1 之后就可以把所有不是 1 的都变了。特判已经存在 1 的情况，只需要求出最小的集合使得其内部的数的 \gcd 为 1。

考虑 DP，设 f_i 为最小的集合使得其内部的数的 \gcd 为 i 的方案数，答案即为 f_1。

考虑判断能否 f_i\leftarrow f_j+1，即要存在 a_x 使得 \gcd(j,a_x)=i。

枚举 i 后只考虑 i 的倍数，尝试直接算 \sum[\gcd(\frac{j}{i},\frac{a_x}{i})=1]，直接上莫反可得 \sum_{d\mid \frac{j}{i},d\mid\frac{a_x}{i}}\mu(d)。

算出 \sum_{d\mid\frac{a_x}{i}}\mu(d) 直接枚举因数即可，时间复杂度 O(\sum_{i=1}^{V}\lfloor\frac{V}{i}\rfloor\log \lfloor\frac{V}{i}\rfloor)=O(V\log^2V)。