题解 CF1139D [Steps to One]
反演套 DP 的好题(不用反演貌似也能做 参考官方 Tutorial
在我的博客查看:传送门
因为每一步不会让已经选了的元素的 $\gcd$ 和变大,因此认为是一个除自环外的有向无环图.对于自环我们很好处理,所以把它看成是一道期望 DP.
令 $f[i]$ 表示当前的 $\gcd$ 和为 $i$,到 $\gcd$ 和为 $1$ 的状态的期望步数.因此把状态转移方程写出来$$ f[i]=1+\frac{\sum_{j=1}^m f[\gcd(i,j)]}m $$ 这样的转移是 $O(m^2)$ 的.但是我们发现,对于很多 $j$,$\gcd(i,j)$ 都是相等的,因