题解：CF1031F Familiar Operations

参考了官方题解。

令 $x=\Pi p_i^{\alpha_i}$，注意到因数个数只和可重集 $\{\alpha_i\}$ 有关，所以只需要保留所有可重集 $\{\alpha_i\}$ 不同的数即可，在 $x\le 10^6$ 条件下共有 $289$ 个，记为 $m$。

容易想到先两两预处理出最短路，然后 $O(1)$ 回答。但是在最短路过程中不一定只经过这 $m$ 个点，有可能终止在范围更大的点。

注意到直接两两跑最短路之后，每个答案都不超过 10，所以新加入的点的 $\sum \alpha_i<30$，这样的点有 $28629$ 个，直接每个点为起点做一次最短路，meet in the middle 即可得到答案。

这样直接跑略多于时限，考虑已有正确做法，将其简化，看答案是否不变。容易发现很多点都是无效的，事实上只有因数个数 $\le 288$ 且 $\sum \alpha_i \le 22$ 的点才有用，于是足以通过。

如果借助因数个数 $\le 288$ （设其与 $m$ 同阶）的性质，可以写出一个 $O(n\log m+m^3+t)$ 或 $O(n\log m+m^2\log m+tm)$ 的 dp 做法，其中 $n=10^6$，也足以通过本题。