dramforever

a row of my life

Möbius 反演

2017-03-18

本文使用 MathJax 渲染公式。如果过了好久以下这行还是不能正常显示那个优美而著名的公式的话，尝试进浏览器调试控制台 Network 栏看看咋回事吧

\sum d | n μ (d) = [n = 1]

这是啥？

一堆 $O (n)$ — $O (\sqrt{n})$ 数论题。

号称是莫比乌斯反演，~~同学都说是容斥是什么情况啊~~

为什么我的眼里常含泪水

因为我过敏
因为 MathJax 一点都不好写（你 Ctrl-U 打开源代码看一下就知道了啊）

Möbius 函数

μ (n) = {\begin{matrix} 0 & n 有非 1 的平方因子 (- 1)^{α} & n 没有非 1 的平方因子，有 α 个质因子 \end{matrix}

当然有些性质

μ (1) = 1

μ (p) = - 1 (p \in P)

那个是“p是质数”的意思

μ (u v) = μ (u) μ (v) (gcd (u, v) = 1)

然后就可以线性筛了对吧

$μ [1] = 1$
For prime $p$ : $μ [p] = 1$
For composite $p u$ :
- if $p | u$ then: $μ [p * u] = 0$
- else: $μ [p * u] = - μ [u]$

好了，知道能算就行了

下面是最重要的那个式子啦

\sum d | n μ (d) = [n = 1]

$[P]$ 表示 $P$ 这个 bool 当 int 使的值

其它的一些基础内容

一般积性函数的线性筛

如果你知道 $F (1)$ ，和如何比较方便地在 $p / | u$ 时算出 $F (p^{α} u)$ ，那么就可以线性筛啦！

方法是，对每个数 $p^{α} u$ 维护这个数的最小质因子 $p$ 是什么（线性筛 ftw），和这个质因子出现了多少次 $α$ （发现（质数 $z$ ） $z | m$ 就 $count [z m] = count [m] + 1$ 就好了），还有除下这么多质数剩下的数 $u$ 。显然还是线性的，而且我们也确实维护出了需要的信息。

\sum i = 1 ⌊ \frac{n}{i} ⌋

（没有上界。因为除着除着就没了）

对于任意一个 $i$ ，从 $i$ 一直到 $⌊ \frac{n}{⌊ n / i ⌋} ⌋$ ， $⌊ \frac{n}{i} ⌋$ 都是一样的。所以我们可以这么着分块算

for (i = 1; i <= n; i = last + 1)
- last = n / (n / i)
- ans += ...

\sum i = 1 ⌊ \frac{n}{i} ⌋ ⌊ \frac{m}{i} ⌋

可以得出 $⌊ \frac{n}{i} ⌋$ 和 $⌊ \frac{m}{i} ⌋$ 总共有 $O (\sqrt{n})$ 个取值（这里假定 $n$ 和 $m$ 同阶）

为什么？因为 $1 n$ 被下取整除法分成 $O (\sqrt{n})$ 段， $1 m$ 也是。总共被砍了 $O (\sqrt{n})$ 刀，还是 $O (\sqrt{n})$ 块。

对于一个 $i$ ，既然 $⌊ \frac{n}{i} ⌋$ 一样的最后一个是 $⌊ \frac{n}{⌊ n / i ⌋} ⌋$ ，那俩都一样的肯定到 $min (⌊ \frac{n}{⌊ n / i ⌋} ⌋, ⌊ \frac{m}{⌊ n / i ⌋} ⌋)$ 呗

枚举的时候要注意啦，for 那里的 i <= n 得 $n \leq m$ 才正常。swap 一下就修好了。

if (n > m) swap (n, m)
for (i = 1; i <= n; i = last + 1)
- last = min (n / (n / i), m / (m / i));
- ans += ...

做题

互质对

n \sum i = 1 m \sum j = 1 [g c d (i, j) = 1]

我们看到了可爱的 $[? ? ? = 1]$

n \sum i = 1 m \sum j = 1 \sum d | g c d (i, j) μ (d)

$d | g c d (i, j)$ 就是两个都整除嘛。

n \sum i = 1 m \sum j = 1 \sum d | i \land d | j μ (d)

我们考虑枚举 $d$

\sum d μ (d) n \sum i = 1 m \sum j = 1 [d | i \land d | j]

只有 $d$ 的倍数的 $i$ 和 $j$ 有贡献。我们偷换变量

$i \to d i$
$j \to d j$

\sum d μ (d) n \sum d i = 1 m \sum d j = 1 [d | d i \land d | d j]

条件永远为真

\sum d μ (d) n \sum d i = 1 m \sum d j = 1 1

$1$ 到 $n$ 有哪些 $d$ 的倍数。嗯这挺好办的。

\sum d μ (d) ⌊ n / d ⌋ \sum i = 1 ⌊ m / d ⌋ \sum j = 1 1

数数好办

\sum d μ (d) ⌊ \frac{n}{d} ⌋ ⌊ \frac{m}{d} ⌋

预处理 $μ$ 前缀和可 $O (n)$ 预处理 $O (\sqrt{n})$ 查询。

给定 $gcd$ 对

n \sum i = 1 m \sum j = 1 [g c d (i, j) = k]

显然 $i$ 和 $j$ 都得是 $k$ 的倍数

n \sum k i = 1 m \sum k j = 1 [g c d (k i, k j) = k]

n \sum k i = 1 m \sum k j = 1 [g c d (i, j) = 1]

$1$ 到 $n$ 里 k 的倍数好啊

⌊ \frac{n}{k} ⌋ \sum i = 1 ⌊ \frac{m}{k} ⌋ \sum j = 1 [g c d (i, j) = 1]

然后就变成上一道题了。结论是

\sum d μ (d) ⌊ \frac{n}{k d} ⌋ ⌊ \frac{m}{k d} ⌋

$gcd$ 求和

n \sum i = 1 m \sum j = 1 g c d (i, j)

考虑枚举 $gcd$ 是啥，数有多少个，乘 $gcd$ 再加起来就是求和啊

\sum g g n \sum i = 1 m \sum j = 1 [g c d (i, j) = g]

代上一题结论

\sum g g \sum d μ (d) ⌊ \frac{n}{g d} ⌋ ⌊ \frac{m}{g d} ⌋

我们枚举 $g d$ 好不好啊

\sum g d (\sum d, g g μ (d)) ⌊ \frac{n}{g d} ⌋ ⌊ \frac{m}{g d} ⌋

这里的枚举 $d, g$ 就是枚举相乘等于 $d g$ 的数啦

预处理里面那个小求和 $F (d g)$ 的前缀和可 $O (n)$ 预处理 $O (\sqrt{n})$ 查询。

注：可以证明 $F (n) = φ (n)$ ，其中 $φ$ 是欧拉函数

$gcd$ 是质数的对数

\sum p \in P n \sum i = 1 m \sum j = 1 [g c d (i, j) = p]

可以推出来一个类似上一题的结论

\sum p d (\sum p \in P, d μ (d)) ⌊ \frac{n}{p d} ⌋ ⌊ \frac{m}{p d} ⌋

（本题中不再赘述 $p$ 是质数）

我们来考虑一下 $F (n) = \sum_{p | n} μ (n / p)$ 的性质。

对于 $z \in P, z / | u$

\begin{matrix} F (z u) & = & \sum_{p | z u} μ (z u / p) = & μ (u) + \sum_{p | u} μ (z u / p) = & μ (u) + \sum_{p | u} - μ (u / p) = & μ (u) - \sum_{p | u} μ (u / p) = & μ (u) - F (u) \end{matrix}

但是如果 $z | u$ ，那么只要 $p \neq z$ ， $z u / p$ 就有平方因子 $z^{2}$ ，所以就挂掉了

\begin{matrix} F (z u) & = & \sum_{p | z u} μ (z u / p) = & μ (u) + \sum_{p | u} μ (z u / p) = & μ (u) \end{matrix}

预处理 $F (p d)$ 的前缀和可 $O (n)$ 预处理 $O (\sqrt{n})$ 查询。

$lcm$ 求和

n \sum i = 1 m \sum j = 1 l c m (i, j)

往下推呗

\begin{matrix} \sum_{i = 1}^{n} \sum_{j = 1}^{m} l c m (i, j) = & \sum_{d} \sum_{i = 1}^{n} \sum_{j = 1}^{m} \frac{i j}{d} [gcd (i, j) = d] = & \sum_{d} \sum_{d i = 1}^{n} \sum_{d j = 1}^{m} \frac{d^{2} i j}{d} [gcd (d i, d j) = d] = & \sum_{d} \sum_{i = 1}^{⌊ n / d ⌋} \sum_{j = 1}^{⌊ m / d ⌋} \frac{d^{2} i j}{d} [gcd (i, j) = 1] = & \sum_{d} d \sum_{i = 1}^{⌊ n / d ⌋} \sum_{j = 1}^{⌊ m / d ⌋} i j [gcd (i, j) = 1] \end{matrix}

然后我们像上面那样枚举 $g c d (i, j) = u$ ， $i$ 偷换成 $u i$ ， $j$ 偷换成 $u j$ 。

\begin{matrix} = & \sum_{u} μ (u) \sum_{d} \sum_{i = 1}^{⌊ n / d u ⌋} \sum_{j = 1}^{⌊ m / d u ⌋} u^{2} d i j = & \sum_{u} μ (u) \sum_{d} u^{2} (\sum_{i = 1}^{⌊ n / d u ⌋} i) (\sum_{j = 1}^{⌊ m / d u ⌋} j) = & \sum_{d u} (\sum_{d, u} d u^{2} μ (u)) \frac{⌊ n / d u ⌋ (1 + ⌊ n / d u ⌋)}{2} \frac{⌊ m / d u ⌋ (1 + ⌊ m / d u ⌋)}{2} = & \sum_{d u} d u (\sum_{d, u} u μ (u)) \frac{⌊ n / d u ⌋ (1 + ⌊ n / d u ⌋)}{2} \frac{⌊ m / d u ⌋ (1 + ⌊ m / d u ⌋)}{2} \end{matrix}

预处理 $d u (\sum_{d, u} u μ (u))$ 前缀和可 $O (n)$ 预处理 $O (\sqrt{n})$ 查询。