题解：CF2115A Gellyfish and Flaming Peony

_O_v_O_ · 2025-06-06 12:20:30 · 题解

很显然当某个数为 \gcd_{i=1}^n a_i 时，那么我们可以用 n-1 次操作即可达成目标。

那么我们就考虑要咋把某个数变成 x=\gcd_{i=1}^n a_i。

假设我们要把 a_1 变成 x，那么题目就等价于选择一个大小最小的集合 S 满足 \gcd\{\gcd_{x\in S} a_x,a_1\}=\gcd_{i=1}^n a_i。

那么我们考虑 dp，设 dp_{i,j} 为前 i 个数，\gcd=j 时最最小集合，那么很显然有 dp_{i,\gcd_{a_i,j}}=\min\{dp_{i,\gcd_{a_i,j}},dp_{i-1,\gcd_{a_i,j}},dp_{i-1,j}+1\}。

预处理 gcd，时间复杂度 O(nV\log V)，常数小所以确实能过。

code