题解：CF1031F Familiar Operations

yingkeqian9217 · 2025-11-17 14:43:50 · 题解

参考了官方题解。

令 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，也足以通过本题。