前置知识
整数分块
整除分块是用于快速处理形似 $\sum_{i = 1}^{n}\lfloor\dfrac{n}{i}\rfloor$ 的式子的方法
很显然，这个可以O(n)得到答案。但是，在某些题目中，毒瘤出题人将数据加强到了 $10^{10}$ 以上，这个时候我们就无法通过O(n)的解法来得到答案了。我们需要一个$O(\sqrt n)$的更为优秀的解法
首先观察这个式子，找几个特殊值代入n=5时，sum=5+2+1+1+1
可以发现的是：（这里给的例子并不明显，其实应该找一个大的n来代入才直观，读者可以自行尝试）
对于单一的$⌊\frac{n}i⌋$，某些地方的值是相同的，并且呈块状分布
通过进一步的探求规律与推理以及打表与瞎猜，我们可以惊喜的发现一个规律，这些块状分布的值是有规律的
对于一个块，假设它的起始位置的下标为l，那么可以得到的是，它的结束位置的下标为$⌊\frac{n}{⌊\frac {n}i⌋}⌋$
如果实在看的有点懵逼，可以继续采用代入特殊值的方法，验证一下上方的规律，用程序表现出来即为
1 | for(int l = 1, r;l <= n;l = r + 1) |
重要函数：
$$
μ(x) = \begin{cases}
0 & (d_i \ge 2)\\
1 & (d_i = 1)
\end{cases}
$$
$$
I = 1
$$
简介
- 莫比乌斯反演主要用来简化运算，通常有性质：
$$
F(n) = \sum_{d|n}f(d) \\
f(n) = \sum_{d|n}μ(d)F(\frac{n}{d})\\
$$
简要证明：
1.直接证
$$
\begin{aligned}
\sum_{d|n}μ(d)F(\frac{n}{d})
&=\sum_{d|n}μ(d)\sum_{i|\frac{n}{d}}f(i)\\
&=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}\mu(d)\\
&=\sum_{i|n}f(i)[\frac{n}{i}==1]\\
&=f(n)\\
\end{aligned}
$$
2.运用狄利克雷卷积
$$
\begin{aligned}
F &= f*I\\
F * \mu &= f * I * \mu \\
(I * \mu) &= \varepsilon \\
F * \mu &= f * \varepsilon = f \\
f &= \mu * F
\end{aligned}
$$
如果看不懂的话, 我将1的详细步骤写一下:
我们将原式化简可得
$$
f(x) = \sum_{d|n}μ(d)\sum_{i| \frac{n}{d}}f(i)
$$
我们令
$$
S(n) = \sum_{d|n}μ(d)
$$
即可化简的
$$
S(n)=[n==1]
$$
我们再令
$$
d = \frac{n}{d}
$$
带回原式可得
$$
f(n) = \sum_{d|n}μ(d)\sum_{i| \frac{n}{d}}f(i)
$$
我们不妨设x = n / d, 则x * d = n, 那么当x确定时，d同样也确定，反之亦然同理, 则f(x)和μ(d)所枚举到的数完全一样，即我们可以交换f(x)和μ(d)，那么原式即可变形为
$$
f(n) = \sum_{i|n}f(i)\sum_{d| \frac{n}{i}}μ(d)
$$
此时我们再联想到S(x), 再令x = n / i, 就可以得到
$$
f(i) = \sum_{i|n}f(i)S(\frac{n}{i})
$$
此时再将F(n)代回
$$
\begin{align}
\sum_{n|d}μ(\frac{d}{n})F(d) &= \sum_{n|d}μ(\frac{d}{n})\sum_{d|i}f(i)\\
&= \sum_{n|i}f(i)\sum_{d| \frac{i}{n}}μ(d) \\
&= f(n)
\end{align}
$$
证毕
例题：luogu P2257 YY的GCD
1 |
|