关于莫比乌斯反演，主要摘自策爷的笔记、知乎–如何证明莫比乌斯反演：

Dirichlet卷积定义：对于数论函数$f$和$g$，他们的卷积为$f*g$为

$$(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$$

---

定义以下函数：

衡为1的常函数$1(n)=1$

恒等函数$id(n)=n$

单位函数$\epsilon(n)=[n=1]$

---

定义莫比乌斯函数：

当$n=1$时，$\mu(1)=1$。

否则将$n$分解成$p_1^{a_1}p_2^{a_2}…p_k^{a_k}$这样的形式，$p_i$为质数，且$a_i$均为$1$时，则$\mu(n)=(-1)^k$。

其余情况$\mu(n)=0$

---

可以得到：

$$1*\mu=\sum_{d\mid n}\mu(d)=\epsilon(n)$$

由二项式定理可证，这个用途在于当存在类似$ \epsilon(gcd(i,j))$这样的函数的时候,可转换成$\sum_{d\mid n}\mu(d)$的形式，用于进一步变换。

而且证明莫比乌斯反演时，这是一个关键步骤。

---

莫比乌斯反演：

$$F(n)=\sum{d\mid n}f(d) \Rightarrow f(n)=\sum{d\mid n}\mu(d)F(n/d)$$

其实也可以写成Dirichlet卷积的形势：$F=1*f$，这样更好证明。

$$F=1*f \Rightarrow \mu*F=\mu*1*f \Rightarrow \mu*F=f$$

---

然后其实莫比乌斯反演还有另外一种形式：

$$F(n)=\sum{n\mid d}f(d) \Rightarrow f(n)=\sum{n\mid d}\mu(\frac{d}{n})F(d)$$

证明：

$$\sum{n\mid d}\mu(\frac{d}{n})F(d) = \sum{n\mid d}\mu(\frac{d}{n})\sum{d\mid m}f(m) =\sum{n\mid m}f(m)\sum_{d\mid \frac{m}{n}}\mu(d)$$

显然当且仅当$m=n$时$\sum_{d\mid \frac{m}{n}}\mu(d)=1$其余为$0$，所以

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d)=f(n)$$

---

例题：3529: [Sdoi2014]数表

大意：$Q$个询问，每个询问给出$n,m,a$。有一张$n*m$的网格，每个格子$(i,j)$的数字为$gcd(i,j)$的约数和。问格子上的数字小于$a$的数字的和，可离线。$ Q \le 2*10^4 ,1 \le n,m \le 10^5, a\le10^9$

题解（参考PoPoQQQ的题解）：

约定$n \le m$，否则交换即可，不影响解。

用$g(k)$表示网格中数字为$k$的数量，记$n’=\lfloor\frac{n}{k}\rfloor$。

$$\begin{split} g(k) =\sum{i=1}^{n}\sum{j=1}^{m}[gcd(i,j)=k] =\sum{i=1}^{n’}\sum{j=1}^{m’}[gcd(i,j)=1] =\sum{i=1}^{n’}\sum{j=1}^{m’}\sum{d\mid gcd(i,j)}\mu(d)=\sum{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor \end{split} $$

用$f(k)$表示$k$的约数和，枚举每个数的倍数可在$O(nlogn)$时间预处理。

那么显然没有a的限制时

$$ \begin{split} ans=\sum{k=1}^{n}f(k)g(k)= \sum{k=1}^{n}f(k)\sum{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor=\sum{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k\mid T}f(k)\mu(\frac{T}{k}) \ \end{split} $$

对于最后一步变换是把$T$替换成$dk$。因为$\lfloor\frac{n}{T}\rfloor$最多有$2\sqrt{n}$种结果，记$h(T)=\sum_{k\mid T}f(k)\mu(\frac{T}{k})$，那么预处理出$h$的前缀和就可以在$O(\sqrt{n})$的时间完成一次询问。

因为存在a的限制，所以可以先给询问按照a排序，然后离线处理。对于每个询问，我们把$k \le a$的插入$h$中，因为需要插入，所以$h$用树状数组来维护。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int L_N = 1e5 + 10;
int mu[L_N], pr[L_N], pn, not_p[L_N];
struct F
{
    int val, id;
    bool operator<(const F &f) const
    {
        return val < f.val;
    }
} f[L_N];
struct Query
{
    int n, m, a, id;
    bool operator<(const Query &q) const
    {
        return a < q.a;
    }
} qs[L_N];
struct TreeArr
{
    int a[L_N];
    int lowbit(int i) { return i & -i; }
    void add(int p, int val)
    {
        for (; p < L_N; p += lowbit(p))
        {
            a[p] += val;
        }
    }
    int query(int p)
    {
        int ret = 0;
        for (; p; p -= lowbit(p))
        {
            ret += a[p];
        }
        return ret;
    }
    int query(int l, int r)
    {
        return query(r) - query(l - 1);
    }
} ta;
void pre()
{
    mu[1] = 1;
    for (int i = 2; i < L_N; i++)
    {
        if (!not_p[i])
            mu[i] = -1, pr[++pn] = i;
        for (int j = 1; j <= pn && ipr[j] < L_N; j++)
        {
            not_p[pr[j] i] = true;
            if (i % pr[j] == 0)
            {
                mu[pr[j] i] = 0;
                break;
            }
            mu[pr[j] i] = -mu[i];
        }
    }

    for (int i = 1; i < L_N; i++)
    {
        f[i].id = i;
        for (int j = i; j < L_N; j += i)
        {
            f[j].val += i;
        }
    }
    sort(f + 1, f + L_N);
}

void insert(F f)
{
    for (int j = f.id; j < L_N; j += f.id)
    {
        ta.add(j, f.valmu[j / f.id]);
    }
}

int sol(int n, int m)
{
    if (n > m)
        swap(n, m);
    int ed = 0, ret = 0;
    for (int t = 1; t <= n; t = ed + 1)
    {
        ed = min(n / (n / t), m / (m / t));
        ret += (n / t)(m / t) * ta.query(t, ed);
    }
    return ret;
}

int ANS[L_N];
int main()
{
    //freopen(“in.txt”,”r”,stdin);

    pre();

    int T;
    scanf(“% d”, &T);
    for (int i = 1; i <= T; i++)
    {
        scanf(“% d % d % d”, &qs[i].n, &qs[i].m, &qs[i].a);
        qs[i].id = i;
    }
    sort(qs + 1, qs + 1 + T);

    int fn = 1;
    for (int i = 1; i <= T; i++)
    {
        Query &q = qs[i];
        while (fn < L_N && f[fn].val <= q.a)
        {
            insert(f[fn]);
            fn++;
        }
        ANS[q.id] = sol(q.n, q.m);
    }

    for (int i = 1; i <= T; i++)
    {
        ANS[i] &= (1 << 31) - 1;
        printf(“% d\n“, ANS[i]);
    }

    return 0;
}