闲停

题目链接：

题意分析：

给出一个空集合和三个操作。操作I向集合中插入元素X，操作D删除集合中的元素X，操作Q，查询集合中与X的最小距离最小是多少？
定义最小距离 $d(x,y)$ 为从x变为y只通过乘或者除素数所需要的最少操作。例如： $d(15, 50) = 3$ ，因为 $15 / 3 \times 2 \times 5 = 50$

解题思路：

求d函数第一反应就是把两个元素分解成质因数，然后去掉公共的部分，剩下的就不是公共部分，必须通过乘法和除法才能变为对方。所以有 $d(x,y) = f(x / gcd(x,y)) + f(y / gcd(x, y))$ 其中 $f(x)$ 是该数的质因子个数。（看到式子感觉确实挺显然的，但比赛中去掉公共部分后就没怎么往这方面想）
考虑枚举x的约数，那么现在问题就在于如何快速的对整个集合中的可行元素求出 $f(y / gcd(x, y))$ 显然，此时只有集合中是约数倍数的数才需要被考虑（这样才能和x一样整除约数）。
尝试定义数组d[i]，代表集合中以i为约数，能达到的最小f值。那么每加入一个集合中不存在的值X，我们就能将X进行约数分解，比如分解成了 $X = y \times z$ ，那么就能这么更新:
d[y] = min(d[y], f[z]); d[z] = min(d[z], f[y]);
然而这样存在一个问题，当能得到最小值的那个元素被删除后，d[]数组的值就不知道该怎么更新了。也许可以记录次小值，那如果次小被删除呢？第三小？所以显然要转换下策略。
由于对于一个数x，他的质因数个数不超过20个（ $2^20 = 1048576$ ），所以我们直接把所有可行值存下来，然后遍历二进制位，找到最小的那一位1所在位置，就是d[]数组对应的值了。所以我们d[]数组存放二进制即可。比如d[3] = 0000101010,那么最小的f值就是1了。
最后我们开个二维数组c[i][j]：记录约数i能得到的f值j出现的次，用它来维护d[]数组的更新即可（次数为0说明不存在了，要剔除）。

个人感受：

这场多校题感觉都好劲啊，那种细细读题解，然后恍然大悟的感觉，那道炉石的DP也是。不像有些场，看了题解一脸懵比。

具体代码链接：

传送门

广告时间

Java学习网站:

VPS: