莫比乌斯反演

前置知识1:整除分块

$①:\lfloor \frac{a}{bc}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}\rfloor$

证明：

$$\frac{a}{b}=\lfloor \frac{a}{b}\rfloor +r,r\in [0,1)$$

$$\lfloor \frac{a}{bc}\rfloor =\lfloor \frac{a}{b}\cdot \frac{1}{c}\rfloor$$

$$=\lfloor \frac{1}{c}\cdot (\lfloor \frac{a}{b}\rfloor +r)\rfloor$$

$$=\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}+\frac{r}{c}\rfloor$$

$$\because r<c$$

$$\therefore \lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}+\frac{r}{c}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}\rfloor$$

$②:i\in [1,n],|\lfloor \frac{n}{i}\rfloor |\le 2\sqrt{n}$

证明：

当 $i\in [1,\lfloor \sqrt{n}\rfloor ]$ 时，$\lfloor \frac{n}{i}\rfloor$有$\lfloor \sqrt{n}\rfloor$种取值

当 $i\in (\lfloor \sqrt{n}\rfloor ,n]$ 时，$\lfloor \frac{n}{i}\rfloor \le \lfloor \sqrt{n}\rfloor$，有$\lfloor \sqrt{n}\rfloor$种取值

$③:$ 对 $\lfloor \frac{n}{i}\rfloor$ 求和， $\forall i\in [1,n]$ 只需要找到最大的一个 $j(i\le j\le n)$，使得 $\lfloor \frac{n}{i}\rfloor =\lfloor \frac{n}{j}\rfloor$，此时 $j=\lfloor \frac{n}{\lfloor \frac{n}{j}\rfloor }\rfloor$

证明：
先证明 $j\ge i$：
$$\lfloor \frac{n}{i}\rfloor \le \frac{n}{i}$$

$$\iff \lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor \ge \lfloor \frac{n}{\frac{n}{i}}\rfloor =\lfloor i\rfloor =i$$

$$\iff i\le \lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor =j$$

再证明最大值
设 $k=\lfloor \frac{n}{i}\rfloor$，则

$$k\le \frac{n}{j}<k+1$$

$$\frac{1}{k+1}<\frac{j}{n}\le \frac{1}{k}$$

$$\frac{n}{k+1}<j\le \frac{n}{k}$$

因为 $j$ 是整数，所以最大值为 $\lfloor \frac{n}{k}\rfloor$

所以每次将 $[i,j]$ 分为一块求解累加到答案上

代码：

for (int l = 1, r; l <= n; l = r + 1) {
   
        r = n / (n / l);
        res += (r - l + 1) * (n / l);
}

前置知识2：莫比乌斯函数

定义：

设 $n=p_1^{c_1}\cdots p_k^{c_k}$
$$\mu (n)=\{\begin{array}{ll}0,& \exists i\in [1,k],c_i>1\\ 1,& k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2),\forall i\in [1,k],c_i=1\\ -1,& k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2),\forall i\in [1,k],c_i=1\end{array}$$

性质：

$$\sum _{d|n}\mu (d)=\{\begin{array}{ll}1,& n=1\\ 0,& n>1\end{array}$$

证明：

$$取n=\prod _{i=1}^k{p}_i$$

$$\sum _{d|n}\mu (d)=\sum _{i=0}^k{C}_k^i\cdot (-1{)}^i$$

$$=(1+(-1){)}^k=0(二项式定理)$$

线性筛莫比乌斯函数：

void get_mobius(int n) {
   
    mobius[1] = 1;
    for (int i = 2; i <= n; i ++) {
   
        if (!st[i]) {
   
            primes[cnt ++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j ++) {
   
            int t = primes[j] * i;
            st[t] = 1;
            if (i % primes[j] == 0) {
   
                mobius[t] = 0;
                break;
            }
            mobius[t] = -mobius[i];
        }
    }
}

莫比乌斯反演：

设 $f(n),g(n)$ 为两个数论函数

形式一：

如果

$$f(n)=\sum _{d|n}g(d)$$

则有

$$g(n)=\sum _{d|n}\mu (d)f(\frac{n}{d})$$

证明：

将

$$f(n)=\sum _{d|n}g(d)$$

带入

$$\sum _{d|n}\mu (d)f(\frac{n}{d})$$

得

$$\sum _{d|n}\mu (d)\sum _{k\mid \frac{n}{d}}g(k)$$

交换求和次序：
因为 $k\mid \frac{n}{d}$ ，那么 $k$ 也是 $n$ 的因子，所以枚举 $n$ 的所有因子 $d$ 等价于枚举 $k$，$k\mid \frac{n}{d}=d\mid \frac{n}{k}$

所以

$$\sum _{k|n}g(k)\sum _{d|\frac{n}{k}}\mu (d)$$

根据 ${\sum }_{d\mid n}\mu (d)=[n=1]$

所以 $n=k$，所以

$$\sum _{k|n}g(k)\sum _{d\mid \frac{n}{k}}\mu (d)=g(n)$$

证毕。

形式二(常用)：

如果

$$f(n)=\sum _{n|d}g(d)$$

则有

$$g(n)=\sum _{n|d}\mu (\frac{d}{n})f(d)$$

证明：

将

$$f(n)=\sum _{n|d}g(d)$$

带入

$$\sum _{n|d}\mu (\frac{d}{n})f(d)$$

得

$$\sum _{n|d}\mu (\frac{d}{n})\sum _{d|k}g(k)$$

交换求和次序：

$$\sum _{n|k}g(k)\sum _{\frac{d}{n}|\frac{k}{n}}\mu (\frac{d}{n})$$

根据 ${\sum }_{d|n}\mu (d)=[n=1]$

所以 $n=k$，所以

$$\sum _{n|k}g(k)\sum _{\frac{d}{n}\mid \frac{k}{n}}\mu (\frac{d}{n})=g(n)$$

证毕。

反演技巧

$$\sum _{i=1}^{n}f(i)\sum _{j=1}^{m}g(j)=\sum _{j=1}^{m}g(j)\sum _{i=1}^{n}f(i)$$

$$\sum _{i=1}^{n}f(i)\sum _{d\mid i}^{m}g(d)=\sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(id)$$