[算法笔记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}(c)$的时间内解决,总时间复杂度为$\mathcal{O}(nc)$,由于$100000$以内的数含有最多的因子数也就100多个,因此时间复杂度上可以接受。

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

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

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

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

1
2
3
4
5
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)$,啊,还是等有时间再学吧。