洛谷5106 - dkw的lcm

积性函数的定义: 如果 $(a,b) = 1$ ,那么 $f(ab) = f(a) \times f(b)$ 。 显然欧拉函数是积性函数。

设 $lcm(i_1, i_2, …, i_k) = x$ ,我们把 $x$ 表示成 $x = \prod {p_i ^ {a_i}}$ 的形式。对每个 $p_i ^ { a_i }$ 分开考虑,枚举每个质数与幂次,用简单容斥统计出每个 $\varphi({p_i ^ {a_i}})$ 在答案中出现的次数,通过欧拉定理 + 快速幂计算答案。

假设我们当前枚举的质数为 $p^k$ ,我们把 $[1..n]$ 的数分成三个集合 $A, B, C$

  • 对于每个 $x \in A$ ,当且仅当 $p^k \not\mid x$;
  • 对于每个 $x \in B$ ,当且仅当 $p^k \mid x$ 且 $p^{k + 1} \not\mid x$ ;
  • 对于每个 $x \in C$ ,当且仅当 $p^{k+1} \mid x$。

则答案中 $\varphi({p^k})$ 的幂次相当于给 $k$ 个空位,只能放集合 $A$ 和 $B$ 中的元素且集合 $B$ 中的元素至少放一次的方案数,即 $(|A| + |B|)^k - |A|^k$,此处的值可能会超过 int 的存储范围,因而根据欧拉定理,对 $\varphi(10^9+7) $ (即 $ 10^9+6$ )取模。

根据小学我们就学过的一个简单公式,如果 $x = \prod p_i ^ { a_i } $ 那么 $x$ 因子个数为 $\prod a_i + 1$ 。因此我们需要维护查询的区间内每一个质数的和。

考虑把原来的数分解,这一步我们只需要预处理出小于 $ \sqrt { \max {a_i} }$ 的质数即可。然后对于每个数 $ a_i $ 依次判断小于 $ a_i $ 的质数。复杂度 $ O( \frac {n \sqrt{\max{a_i}}} {\log n} )$ ,实际情况下表现非常优越。或者采用 Pollard-Rho 算法优化为 $ n \times \sum { a_i^{ 1 / 4 } }$ ,但实现会较为复杂而且没有必要。

接下来考虑分解出的质数如何处理,如果直接放在一起去莫队的话复杂度是 $ O(n \sqrt n \log n) $ ,如果常数不优秀的话会 TLE 。我们考虑一个优化方式,对于大小在前 $\sqrt n$ 个的范围内的质数,预处理出个数,前缀和统计,不参与莫队,其余分解出的质数参与莫队,可以证明,每一个数需要参与莫队的数的个数是 $O(1)$ 级别的。这样的话复杂度降为 $n \sqrt n$ ,事实上我们可以把范围由 $\sqrt n$ 调整为 $100$ ~ $200$ 左右以获得一个较小的常数,跑到目前效率 rank 1。

欧拉筛求质数

欧拉筛是一种优秀的筛质数方法。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×