[算法笔记3]Codeforces - 1139 D. Steps to One

如何求出1-n每个数的全部因子？
在继续往下阅读之前，请先想一想，如果给定一个$n,n\leq100000$，让你求出1~n的全部因子，你需要如何实现？要编写多少行代码？复杂度如何？

可能会这么考虑，如果对于每个数$x$，枚举1~n逐一判断每个数是否是$x$的因子，复杂度为$\mathcal{O}(n^2)$，显然是不可接受的，即使枚举到$\sqrt n$，复杂度也有$\mathcal{O}(n \sqrt n)$，依然太大，有没有更好的办法？

在我一开始解决这个问题的时候，我先求出了1-n的全部素数，这在$\mathcal{O}(n)$时间内可以解决，然后对1-n中的每个数因式分解，注意到每个数$x$可以写成

$$x=p_1^{q_1}*p_2^{q_2}*...*p_k^{q_k}$$

的形式，所以$x$共有$c=(q_1+1)*(q_2+1)*…*(q_k+1)$个因数，穷举这些因数，所以每个数可以在$\mathcal{O}(\textrm{c})$的时间内解决，总时间复杂度为$\mathcal{O}(nc)$，由于$100000$以内的数含有最多的因子数也就100多个，因此时间复杂度上可以接受。

听起来很合理是吗？然鹅，我写到一半就写不下去了。因为……实！现！起！来！太！麻！烦！了！

维护好素数表之后，你要对每个数因式分解，然后遍历统计出$q_1,q_2,…,q_k$的值，其中有些值还是0，为了去掉这些0加快穷举速度，你需要用一个map<int,int>记录$p_i,q_i$，然后怎么穷举因子呢？还要再写一个dfs遍历map……

太麻烦了吧！有没有什么好办法呢？就是那种……很简单的……只需要几行代码就能全部搞定的那种

其实只需要三行就能搞定啦

for (int i = 2; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
        fact[j].push_back(i);
    }
}

这个方法其实和使用筛法求素数是一模一样的，就是1-n的每个因子$x$一定是$kn$的一个因子，所以遍历所有因子，计算这些因子的倍数并加上这些因子就可以了。可以算出总操作次数为$n(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n})$，由欧拉公式大概可以估计出，总复杂度为$\mathcal{O}(nlogn)$

好了，至于本文的标题Codeforces - 1139 D. Steps to One其实并不是求个因子就完事啦，这题还要用容斥原理+dp求解，但这些都不是重点了，所以我们就一笔带过吧。设$dp[x]$表示当前gcd为x时的期望长度，则dp方程如下

$$dp[x]=1+\sum_{i \in divisor(x)}\frac{f(x,i)*dp[i]}{m}$$

其中$f(x,i)$是指满足$gcd(x,k)=i,1\leq k \leq m$的$k$的个数，$f(x,i)$可以通过容斥原理在线性时间内求出，最后的答案为

$$answer=1+\sum_{i=1}^{m}\frac{dp[i]}{m}$$

虽然看起来不容易，我也以为有点难，但是实现起来不是很复杂，很快就可以写完了(并不)

这题还可以用莫比乌斯反演来求$f(x,i)$，啊，还是等有时间再学吧。