求d函数第一反应就是把两个元素分解成质因数,然后去掉公共的部分,剩下的就不是公共部分,必须通过乘法和除法才能变为对方.所以有 $d(x,y) = f(x / gcd(x,y)) + f(y / gcd(x, y))$ 其中 $f(x)$ 是该数的质因子个数.(看到式子感觉确实挺显然的,但比赛中去掉公共部分后就没怎么往这方面想)
然而这样存在一个问题,当能得到最小值的那个元素被删除后,d[]数组的值就不知道该怎么更新了.也许可以记录次小值,那如果次小被删除呢?第三小?所以显然要转换下策略.