[算法笔记 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$ 共有 $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……

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

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

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 方程如下

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

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

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

评论