洛谷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$ )取模。

Your browser is out-of-date!

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

×