题意简述
Gellyfish 讨厌数学题，但她必须完成她的数学作业：
Gellyfish 得到一个长度为 $n$ 的正整数数组 $a_1,a_2,\dots,a_n$。
她需要重复进行如下两步操作，直到数组 $a$ 的所有元素都相等为止：
- 选择两个下标 $i,j$，满足 $1 \leq i,j \leq n$ 且 $i \neq j$；
- 将 $a_i$ 替换为 $\gcd(a_i,a_j)$。
现在，Gellyfish 想知道，使得所有元素相等所需的最少操作次数是多少。
可以证明，Gellyfish 总是能够实现她的目标。
思路分析
容易知道，最后所有元素一定是 $\gcd\limits_{i=1}^n(a_i)$。记这个值为 $g$。
为了方便，记 $b_i \gets \dfrac{a_i}{g}$。
这样之后 $g_b=1$.
记 $\text{cnt}$ 表示 $b$ 数组中非 $1$ 元素的个数。
如果现在的 $b_i$ 中存在 $1$，那么我们只需要将所有的非 $1$ 值与它求一次 $\gcd$ 即可。
如果不存在，那么就要凑出来一个 $1$。
问题就转化为了如何用最少的操作数凑出来一个 $1$。
记 $f(x)$ 表示在 $b$ 内，得到一个 $x$，所需要的最少操作数。
那么 $f(\gcd(x, b_i))=\min(f(\gcd(x,b_i)), f(x) + 1)$。
这个式子的意思就是，通过 $b_i$ 去和所有的 $x$ 求 $\gcd$，然后更新对应的值。
最终答案就是 $f(1) + (N-2)$.
总结
想不到用 dp 啊，，，
从一个状态花费一定代价转移到另一个状态，然后求到达某个状态的最小代价？
这不 BFS 吗。
好像也对，初始状态是 $b$ 的所有值，然后每一个值拿出来和目前的值域都求一遍 $\gcd$，获得的值只会不增，最后应该会收敛到 $1$。
看起来是合理的。
哦对的对的。