版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 笔记 - 关于 gcd 求和与计数的问题 categories:
总结一些 Möbius 反演中一些关于 gcd 求和与计数问题的解法
<!-- more -->即形如
$$ \sum{\nu\in\prod{i=1}^m[1,ni]\mathbb{N}}f(\nu)g(\gcd\nu) $$
的和式, 其中
令 $n0=\min{i=1}^mn_i$, $gn=\gcd{i=1}^mn_i$, 则我们可以按如下方法处理
$$ \begin{aligned} \sum{\nu\in\prod{i=1}^m[1,ni]\mathbb{N}}f(\nu)g(\gcd\nu)&=\sum_{d=1}^{n0}g(d)\sum{\nu\in\prod_{i=1}^m[1,ni]\mathbb{N}}f(\nu)[\gcd\nu=d]&(1)\ &=\sum_{d=1}^{n0}g(d)\sum{\nu\in\prod_{i=1}^m[1,\lfloor\frac{ni}{d}\rfloor]\mathbb{N}}f(d\nu)[\gcd\nu=1]&(2)\ &=\sum_{d=1}^{n0}g(d)\sum{\nu\in\prod_{i=1}^m[1,\lfloor\frac{ni}{d}\rfloor]\mathbb{N}}f(d\nu)\sum{e\mid\gcd\nu}\mu(e)&(3)\ &=\sum{d=1}^{n0}g(d)\sum{e=1}^{ \frac{gn}{d}}\mu(e)\sum{\nu\in\prod_{i=1}^m[1,\lfloor\frac{ni}{de}\rfloor]\mathbb{N}}f(de\nu)&(4)\ &\xlongequal[D=de]{F(x)=\sum{\nu\in\prod{i=1}^m[1,\lfloor\frac{ni}{x}\rfloor]\mathbb{N}}f(x\nu)}\sum_{D=1}^{n_0}F(D)(g*\mu)(D)&(5)\ \end{aligned} $$
其中
$(2)$: 将 $[\gcd\nu=d]$ 化为 $[\gcd\nu=1]$, 以便于使用等式
$$ \mu*{1}=\epsilon $$
$(3)$: 使用上述等式
由 $F(x)$ 的定义, 我们发现该和式可以使用数论分块来加速
实际题目中,
即形如
$$ \sum{\nu\in\prod{i=1}^m[1,ni]\mathbb{N}}[\gcd\nu\in K={k_1,k_2,\dots,k_s}] $$
的和式, 其中
令 $n0=\min{i=1}^mn_i$, $gn=\gcd{i=1}^mn_i$, 则我们可以按如下方法处理
$$ \begin{aligned} \sum{\nu\in\prod{i=1}^m[1,ni]\mathbb{N}}[\gcd\nu\in K]&=\sum{k\in K}\sum{\nu\in\prod_{i=1}^m[1,ni]\mathbb{N}}[\gcd\nu=k]\ &=\sum_{D=1}^{n0}\left(\prod{i=1}^m\left\lfloor\frac{ni}{D}\right\rfloor\right)\sum{k\mid D;~k\in K}\mu\left(\frac{D}{k}\right) \end{aligned} $$
具体推导看上一节即可, 可看作 $f(x)=1$, $g(x)=\epsilon(x)$ 的特例