莫比乌斯反演(1)
1.狄利克雷生成函数
数列 $\langle a_1,a_2,\cdots \rangle$ 的狄利克雷生成函数为:
$$
F(x) = \frac{a_1}{1^x} + \frac{a_2}{2^x} + \cdots = \sum_{n = 1}^\infty \frac{a_n}{n^x}
$$
两个狄利克雷生成函数的乘法运算为:
$$ \begin{align} \sum_{i = 1}^\infty \frac{a_i}{i^x} &\sum_{j = 1}^\infty \frac{b_j}{j^x}\\\\ &=\Big(\frac{a_1}{1^x} + \frac{a_x}{2^x} + \cdots \Big) \Big( \frac{b_1}{1^x} + \frac{b_2}{2^x} + \cdots\Big)\\\\ &= \frac{a_1 b_1}{1^x} + \frac{a_1 b_2 + a_2b_1}{2^x} + \frac{a_1b_3 + a_3b_1}{3^x} + \cdots\\\\ &= \sum_{n = 1}^\infty \frac{1}{n^x} \sum_{d | n} a_d b_{\frac{n}{d}} \end{align} $$
事实上,对于 $\displaystyle \frac{1}{G^x}$ 的系数只需要枚举 $G$ 的所有约数:
$\rm Ex. \displaystyle \frac{1}{6^x}$的系数为 $a_1b_6 + a_2b_3 + a_3b_2 + a_6 b_1$
2. 积性函数
定义:$f(1) = 1$,当 $\rm gcd(a,b)=1$ 有 $f(ab)=f(a)f(b)$,则 $f(n)$ 为积性函数
欧拉函数和莫比乌斯函数都是积性函数
2.1 欧拉函数
定义:
$$
\phi(n) = \sum_{i = 1}^n [\mathrm{gcd}(i, n) = 1]
$$
性质: $\displaystyle \sum_{d | n} \phi(d) = n$
$\phi(1) + \phi(2) + \phi(3) + \phi(6) = 6$
2.2 莫比乌斯函数
定义:
$$ \mu(n) = \begin{cases} 1 & n = 1\\\\ (-1)^s & n = p_1p_2,\cdots p_s \\\\ 0 & \mbox{n包含相同质因子}\end{cases} $$
性质:
$$
\sum_{d | n} \mu(d) = [n = 1]
$$
联系(欧拉函数性质反演结论):
$$ \sum_{d | n} \mu(d) \frac{n}{d} = \phi(n) $$
3. 狄利克雷卷积
定义:$f(n),g(n)$ 是两个积性函数:
$$
(f * g)(n) = \sum_{d | n} f(d) g(\frac{n}{d}) = \sum_{d | n} f(\frac{n}{d}) g(d)
$$
ex: $(f * g)(4) = f(1)g(4) + f(2)g(2) + f(4)g(1)$
性质:
-
交换律: $f * g = g * f$
-
结合律: $(f * g) * h = f * (g * h)$
-
分配律: $(f + g) * h = f * h + g * h$
常用函数:
-
元函数: $\epsilon(n) = [n = 1]$
-
常数函数: $1(n) = 1$
-
恒等函数: $ \mathrm{id}(n) = n$
常用卷积关系:
-
$\displaystyle \sum_{d | n} \mu(d) = [n = 1] \Leftrightarrow \mu * 1= \epsilon$
-
$\displaystyle \sum_{d | n} \phi(d)=n \Leftrightarrow \phi * 1 = \mathrm{id}$
-
$\displaystyle \sum_{d | n} \mu(d) \frac{n}{d} = \phi(n) \Leftrightarrow \mu * \mathrm{id} = \phi$
-
$\displaystyle f * \epsilon = f$
-
$\displaystyle f * 1 \ne f$
4. 和式的变换技术
1.替换条件式
$$ \sum_{i = 1}^n\sum_{j = 1}^m \sum_{d | \mathrm{gcd}(i,j)} d = \sum_{i = 1}^n \sum_{j = 1}^m \sum_{d = 1}^n [d | i][d | j] d $$
2.替换指标变量
$$ \sum_{i = 1}^n \sum_{j = 1}^m [\mathrm{gcd}(i,j)=k] = \sum_{ik = 1}^n \sum_{jk = 1}^m [\mathrm{gcd}(ik,jk) = k] $$
Q1.求 $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^m [\mathrm{gcd}(i,j)=k]$ From Luogu P3455
A.定义$n’ = n / k,m’ = m / k$(下取整)
$$ \begin{align} \mathrm{LHS} &= \sum_{i = 1}^{n’} \sum_{j = 1}^{m’} \epsilon(\mathrm{gcd(i,j)})\\\\ &= \sum_{i = 1}^{n’} \sum_{j = 1}^{m’} \mu * 1 = \sum_{i = 1}^{n’} \sum_{j = 1}^{m’} \sum_{d | \mathrm{gcd(i,j)}} \mu(d) \\\\ &= \sum_{i = 1}^{n’} \sum_{j = 1}^{m’} \sum_{d = 1}^{n’} [d | i][d | j] \mu(d)\\\\ &= \sum_{d = 1}^{n’} \mu(d)\sum_{i = 1}^{n’} [d | i] \sum_{j = 1}^{m’} [d | j]\\\\ &= \sum_{d = 1}^{n’} \mu(d) \lfloor \frac{n’}{d} \rfloor \lfloor \frac{m’}{d} \rfloor \end{align} $$
注意到有 $\displaystyle \sum_{i = 1}^n f(i)\lfloor \frac{n}{i} \rfloor$ 形式,可以采取 整除分块
Q2. 求 $\displaystyle \sum_{i=1}^n \sum_{j = 1}^m [\mathrm{gcd}(i,j) \in \mathrm{prim}]$ From Luogu P2257
A.
$$
\begin{align}
\mathrm{LHS} &= \sum_{k = 1}^n \sum_{i= 1}^n \sum_{j = 1}^m [\mathrm{gcd}(i,j) = k][k \in \mathrm{prim}]\\\\
&= \sum_{k = 1}^n\sum_{i= 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [\mathrm{gcd}(i,j) = 1][k \in \mathrm{prim}]\\\\
&= \sum_{k = 1}^n\sum_{i= 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \sum_{d | \mathrm{gcd(i,j)}} \mu(d) [k \in \mathrm{prim}]\\\\
&= \sum_{k = 1}^n\sum_{i= 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} [d | i][d | j]\mu(d) [k \in \mathrm{prim}]\\\\
&= \sum_{k = 1}^n [k \in \mathrm{prim}] \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \sum_{i= 1}^{\lfloor \frac{n}{k} \rfloor} [d | i] \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}[d | j]\\\\
&= \sum_{k = 1}^n [k \in \mathrm{prim}] \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
\end{align}
$$
取 $T = kd,d = T / k$
$$ \begin{align} \mathrm{LHS} &= \sum_{k = 1}^n [k \in \mathrm{prim}] \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \\\\ &= \sum_{k = 1}^n [k \in \mathrm{prim}] \sum_{T/k = 1}^{\lfloor \frac{n}{k} \rfloor}\mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \\\\ &= \sum_{k = 1}^n [k \in \mathrm{prim}] \sum_{T= 1}^{n}\mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \\\\ &= \sum_{T= 1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{k = 1}^n \mu(\frac{T}{k}) [k \in \mathrm{prim}]\\\\ &= \sum_{T = 1}^n \sum_{k \in \mathrm{prim}} \mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \\\\ &= \sum_{T = 1}^n {\color{red}{F(T)}} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \end{align} $$
其中 $\displaystyle {\color{red}{F(T)}} = \sum_{k \in \mathrm{prim}} \mu(\frac{T}{k}) $,$F(T)$ 前缀和预处理后然后使用整除分块
Q3. 设 $d(x)$ 为 $x$ 的约数个数,给定 $n,m$ 求 $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^m d(ij)$ From Luogu P3327
引理: $\displaystyle d(ij) = \sum_{x | i} \sum_{y | j} [\mathrm{gcd}(i,j) = 1]$
对于 $ij$ 的一个约数 $\prod_a p_a^{c_m}$ ,假设 $i = \prod_a p_a^{c_n},j = \prod_a p_a^{c_k}$,可以按照如下方法构造与其唯一对应的 $(x,y)$ 对:
-
如果$c_m \leq c_n$,$x$ 则包含 $p_a^{c_m}$,$y$ 则包含 $p_a^0 = 1$
-
否则,$x$ 包含 $p_a^{c_n}$,$y$ 包含 $p_a^{c_m - c_n}$
注意到以上构造方式对于每个约数而言是唯一的
另外由于每个数字可以由质因数分解唯一确定,我们可以,使得操作 $2$ 中的 $x$ 不包含$p_a^{c_n}$,而是包含 $1$,这样仍然能够通过 $y$ 的 $p_a^{c_m - c_n}$,推出该约数字对于 $p_a$ 的指数为 $c_m - c_n + c_n = c_m$,所以仍然保证唯一性
$$ \begin{align} &\sum_{i = 1}^n\sum_{j=1}^m d(ij)\\\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i}\sum_{y|j} [\mathrm{gcd}(x,y)=1]\\\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{x = 1}^n \sum_{y=1}^m [x|i][y|j][\mathrm{gcd}(x,y)=1]\\\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{x = 1}^n \sum_{y=1}^m [x|i][y|j] \sum_{d | \mathrm{gcd}(x,y)} \mu(d)\\\\ &= \sum_{x = 1}^n \sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{n}{y} \rfloor \sum_{d=1}^n [d | x][d | y]\mu(d)\\\\ &= \sum_{d = 1}^n \mu(d) \sum_{x = 1}^n \sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{n}{y} \rfloor [d | x][d | y]\\\\ &= \sum_{d = 1}^n \mu(d) \sum_{x = 1}^n \lfloor \frac{n}{x} \rfloor [d | x] \sum_{y=1}^m \lfloor \frac{n}{y} \rfloor [d | y]\\\\ & x \rightarrow \mathrm{d}x,y \rightarrow \mathrm{d}y\\\\ &= \sum_{d = 1}^n \mu(d) \sum_{dx = 1}^n \lfloor \frac{n}{dx} \rfloor \sum_{dy=1}^m \lfloor \frac{m}{dy} \rfloor\\\\ &= \sum_{d = 1}^n \mu(d) \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \sum_{y = 1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{dy} \rfloor \\\\ & \mathrm{set}\quad F(x) = \sum_{l = 1}^x \lfloor \frac{x}{l} \rfloor\\\\ &= \sum_{d = 1}^n \mu(d) F(\lfloor \frac{n}{d} \rfloor) F(\lfloor \frac{m}{d} \rfloor) \end{align} $$
预处理 $\mu,F$ 后整除分块
%%%