莫比乌斯反演学习笔记

概念

莫比乌斯函数 $\mu (n)$，是一个积性函数，定义为：
$$\mu (n)=\{\begin{array}{l}1,n=1\\ 0,nisdivisiblebythesquareofaprimenumber\\ (-1{)}^k,kisthenumberofprimefactorsofn\end{array}$$

其性质有：一、${\sum }_{d|n}\mu (d)=[n=1]$；二、$\mu \ast 1=ϵ$，其中 $\ast$ 表示狄利克雷卷积，$ϵ=[n=1]$（其实这条与一等价）

莫比乌斯反演的形式有二：一、设 $F(n)={\sum }_{n|m}f(m)$，有 $f(n)={\sum }_{n|m}F(m)\mu (\frac{m}{n})$；二、设 $F(n)={\sum }_{m|n}f(m)$，有 $f(n)={\sum }_{m|n}F(\frac{n}{m})\mu (m)={\sum }_{m|n}F(m)\mu (\frac{n}{m})$；

例题

1. Luogu P2257 YY的GCD

题意

给定 $N,M$，求 $1\le x\le n$，$1\le y\le m$ 且 $\gcd (x,y)$ 为质数的 $(x,y)$ 有多少对。

$T=10^4;n,m\le 10^7$。

做法

设 $f(p)={\sum }_{x=1}^n{\sum }_{y=1}^m[\gcd (x,y)=p];F(p)={\sum }_{p|q}f(q)=\lfloor \frac{n}{p}\rfloor \lfloor \frac{m}{p}\rfloor ;L=\min (n,m)$。

即求：

$$\begin{gathered} \sum _{p\in Prime}f(p) \\ =\sum _{p\in Prime}\sum _{p|x}F(x)\mu (\frac{x}{p}) \\ =\sum _{p\in Prime}\sum _{i=1}^{L/p}\lfloor \frac{n}{ip}\rfloor \lfloor \frac{m}{ip}\rfloor \mu (i) \\ =\sum _{T=1}^L\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \sum _{p|T\&p\in Prime}\mu (\frac{T}{p}) \end{gathered}$$

重点在于求 $g(x)\triangleq {\sum }_{p|x\&p\in Prime}\mu (\frac{x}{p})$。$p$ 是 $x$ 的一个质因数，考虑通过某种顺序枚举 $x$ 的质因数，发现线性筛的过程会将 $x$ 拆成一个最小的质因数和另一个数的乘积，即 $x=y\cdot p,p\in Prime$，则有：
$$g(x)=\{\begin{array}{l}\mu (1),x\in Prime\\ g(y),pisafactorofy\\ -g(y)+\mu (y),pisnotafactorofy\end{array}$$
需要注意从 $-g(y)$ 转移因为 $g(y)$ 所包含的 $\mu$ 与 $g(x)$ 所包含的 $\mu$ 差一个因子 $p$。

代码

#include <bits/stdc++.h>

const int N = 1e7;

int mu[N + 2], prime[N + 2], top, sum[N + 2];
bool nprime[N + 2];

void solve() {
    int n, m;
    std::cin >> n >> m;
    long long ans = 0;
    for (int l = 1, r; l <= std::min(n, m); l = r + 1) {
        r = std::min(n / (n / l), m / (m / l));
        ans += 1ll * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!nprime[i]) {
            prime[++top] = i;
            mu[i] = -1;
            sum[i] = 1;
        }
        for (int j = 1; j <= top && 1ll * i * prime[j] <= N; j++) {
            int now = i * prime[j];
            nprime[now] = 1;
            if (i % prime[j] == 0) {
                mu[now] = 0;
                sum[now] = mu[i];
                break;
            }
            mu[now] = -mu[i];
            sum[now] = mu[i] - sum[i];
        }
    }
    for (int i = 1; i <= N; i++) {
        sum[i] += sum[i - 1];
    }
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

2. Luogu P2522 [HAOI2011] Problem b

题意

对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a\le x\le b$，$c\le y\le d$，且 $\gcd (x,y)=k$。

$1\le n,k\le 5\times 10^4$，$1\le a\le b\le 5\times 10^4$，$1\le c\le d\le 5\times 10^4$。

做法

（这个感觉比上面一个更加板子）

可以 $a^{\prime }\leftarrow \lceil \frac{a}{k}\rceil ,b^{\prime }\leftarrow \lfloor \frac{b}{k}\rfloor$ 这样操作把 $k$ 转换为 $1$，然后对于两个区间可以容斥为 $res(b^{\prime },d^{\prime })-res(a^{\prime }-1,d^{\prime })-res(b^{\prime },c^{\prime }-1)+res(a^{\prime }-1,c^{\prime }-1)$。即求 ${\sum }_{x=1}^n{\sum }_{y=1}^m[\gcd (x,y)=1]={\sum }_{i=1}^{\min (n,m)}\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor \mu (i)$。

代码

#include <bits/stdc++.h>

const int N = 5e4;

int mu[N + 2], prime[N + 2], top, sum[N + 2];
bool nprime[N + 2];

long long work(int n, int m) {
    long long ans = 0;
    if (n > m) {
        std::swap(n, m);
    }
    for (int l = 1, r; l <= n; l = r + 1) {
        r = std::min(n / (n / l), m / (m / l));
        ans += 1ll * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
    }
    return ans;
}

void solve() {
    int a, b, c, d, k;
    std::cin >> a >> b >> c >> d >> k;
    a = (a + k - 1) / k;
    c = (c + k - 1) / k;
    b = b / k;
    d = d / k;
    std::cout << (work(b, d) - work(a - 1, d) - work(b, c - 1) + work(a - 1, c - 1)) << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!nprime[i]) {
            prime[++top] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= top && 1ll * i * prime[j] <= N; j++) {
            int now = i * prime[j];
            nprime[now] = 1;
            if (i % prime[j] == 0) {
                mu[now] = 0;
                break;
            }
            mu[now] = -mu[i];
        }
    }
    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i - 1] + mu[i];
    }
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}