传送门
Solution
之前有遇到类似的题，第一步先考虑转化操作和问题。
对于每个数质因数分解成 \prod{p_i^{\alpha_i}}，我们所需要的只有 \alpha_i，因为只要求因子个数相同。
记其为 S_i = \{\alpha_1,\alpha_2,\dots,\alpha_k\}，其中 \alpha_1 \geq \alpha_2 \geq \dots \alpha_k。
将操作进行转化，对于操作一，它等效于对于集合 $S_i$ 中一个 $\alpha_i + 1$，对于操作二，它等效于新建了一个质因数。
考虑转移至目标状态，记 $dp_{S_i,j}$ 表示由集合 $S_i$ 转移至含有 $j$ 个因数状态的最小操作数，对于初始的 $dp_{S_1,0} = 0$，我们首先考虑 $S_1$ 的转移，以下记 $minp_i$ 表示 $i$ 中最小的质因数：
$$
dp_{S_1,i} = dp_{S_1,\frac{i}{minp_i}} + minp_i - 1
$$
意为在目标质因数个数为 $\frac{i}{minp_i}$ 时，需要 $minp_i - 1$ 个因数来转移到 $j$。
**为什么这样转移一定最优呢？**
操作二每次新建质因数，即因数数量改变，故向最终答案逼近的越快。
现在考虑 $dp_{S_i,j}$ 的转移，依据刚才的最优转移，得出：
> 我们所期望的最优方案，是存在质因数 $p$，在 $i$ 中出现过，$j$ 中不含，且在 $i$ 中出现次数最小，因为从 $S_j \to S_i$ 的转移的花费为其出现次数。
故转移即可。
**但是若 $p$ 不存在呢？**
对于方才的转移我们可以看做操作一，即修改 $\alpha_i$ 最小的质因数，现在就是操作二，我们枚举新增质因数的倍数进行转移即可，即从 $S_{k \times j} \to S_{j}$，其中 $k \in [2,M]$。
用 vector 存储状态和 dp 值，用 map 映射，预处理，随后每次询问取最小值即可。（注意不能转移直接调用 dp，因为每次是 $\log n$ 的，很劣，复制一遍存下来，这样就是 $O(1)$ 的查询）。
总复杂度 $O(nM\sqrt{M} + tM)$。
## Code
[Submission](https://codeforces.com/contest/1071/submission/300243565)