跳转至

莫比乌斯函数

定义

\[ \begin{equation} \mu(n)= \begin{cases} 1&&n=1\\ {(-1)}^r&&n=p_1^1*p_2^1*…*p_r^1\\ 0&&else \end{cases} \end{equation} \]

定理

\[ \begin{equation} \sum_{d|n}\mu(d)= \begin{cases} 1&&n=1\\ 0&&n>1 \end{cases} \end{equation} \]
筛法求莫比乌斯函数
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace MobiusSieve {
    vector<int> prime;
    vector<int> vis;
    vector<int> mob;
    void init(const int N) {
        prime.resize(0);
        vis.resize(0);
        vis.resize(N + 1);
        mob.resize(0);
        mob.resize(N + 1);
        mob[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            if (vis[i] == 0) {
                vis[i] = i;
                prime.push_back(i);
                mob[i] = -1;
            }
            for (auto &x : prime) {
                if (1LL * i * x > N) break;
                vis[i * x] = x;
                if (i % x == 0) {
                    mob[i * x] = 0;
                    break;
                }
                mob[i * x] = -mob[i];
            }
        }
    }
} // MobiusSieve

莫比乌斯变换

① 如果 \(f(n)=\sum_{d|n}g(d)\)，那么 \(g(n)=\sum_{d|n}\mu(d)*f(\frac{n}{d})\)

② 如果 \(f(n)=\sum_{n|d}g(d)\)，那么 \(g(n)=\sum_{n|d}\mu(\frac{d}{n})*f(d)\)

莫比乌斯反演

\[ [\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d) \]
题单

莫比乌斯反演（函数）练习题单 - 题单 - 洛谷

P2257 YY的GCD - 洛谷

\[ \begin{align} &\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in prime]\\ &=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]&(k\in prime)\\ &=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]&(k\in prime)\\ &=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d)&(k\in prime)\\ &=\sum_{k=1}^{\min(n,m)}\sum_{d=1}^{\lfloor\frac{\min(n,m)}{k}\rfloor}\mu(d)*\lfloor\dfrac{n}{kd}\rfloor*\lfloor\frac{m}{kd}\rfloor&(k\in prime)\\ \end{align} \]

令 \(T=k*d\)

\[ \begin{align} &=\sum_{k=1}^{\min(n,m)}\sum_{d=1}^{\lfloor\frac{\min(n,m)}{k}\rfloor}\mu(\frac{T}{k})*\lfloor\dfrac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor&(k\in prime)\\ &=\sum_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor*\sum_{k|T,k\in prime}\mu(\frac{T}{k}) \end{align} \]

令 \(f(x)=\sum_{k|x,k\in prime}\mu(\frac{x}{k})\)

可以发现通过枚举质数 \(k\) 的倍数来做前缀和预处理 \(f(x)\)

\[ \begin{align} &=\sum_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor*f(T) \end{align} \]
代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
namespace MobiusSieve {
    vector<int> prime;
    vector<int> vis;
    vector<int> mob;
    vector<i64> sum;
    void init(const int N) {
        prime.resize(0);
        vis.resize(0);
        vis.resize(N + 1);
        mob.resize(0);
        mob.resize(N + 1);
        sum.resize(0);
        sum.resize(N + 1);
        mob[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            if (vis[i] == 0) {
                vis[i] = i;
                prime.push_back(i);
                mob[i] = -1;
            }
            for (auto &x : prime) {
                if (1LL * i * x > N) break;
                vis[i * x] = x;
                if (i % x == 0) {
                    mob[i * x] = 0;
                    break;
                }
                mob[i * x] = -mob[i];
            }
        }
        for (auto &x : prime) {
            int i = 1;
            while (1LL * i * x <= N) {
                sum[i * x] += mob[i];
                i++;
            }
        }
        for (int i = 1 ; i <= N ; i++) {
            sum[i] += sum[i - 1];
        }
    }
} // MobiusSieve
int main() {
    MobiusSieve::init(10000000);
    using MobiusSieve::sum;
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n > m) swap(n, m);
        i64 ans = 0;
        for (int L = 1, R ; L <= n ; L = R + 1) {
            R = min(n / (n / L), m / (m / L));
            ans += (sum[R] - sum[L - 1]) * (n / L) * (m / L);
        }
        cout << ans << "\n";
    }
    return 0;
}

P2522 [HAOI2011] Problem b - 洛谷

\[ \begin{align} F(x,y)&=\sum_{i=1}^x\sum_{j=1}^y[\gcd(i,j)=1]\\ &=\sum_{i=1}^x\sum_{j=1}^y\sum_{d|\gcd(i,j)}\mu(d)\\ &=\sum_{d=1}^{min(x,y)}\mu(d)*\lfloor\frac{x}{d}\rfloor*\lfloor\frac{y}{d}\rfloor \end{align} \]
\[ \sum_{i=x}^n\sum_{j=y}^m[\gcd(i,j)=k]=F(\frac{n}{k},\frac{m}{k})-F(\frac{x-1}{k},\frac{m}{k})-F(\frac{n}{k},\frac{y-1}{k})+F(\frac{x-1}{k},\frac{y-1}{k}) \]
代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
namespace MobiusSieve {
    vector<int> prime;
    vector<int> vis;
    vector<int> mob;
    void init(const int N) {
        prime.resize(0);
        vis.resize(0);
        vis.resize(N + 1);
        mob.resize(0);
        mob.resize(N + 1);
        mob[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            if (vis[i] == 0) {
                vis[i] = i;
                prime.push_back(i);
                mob[i] = -1;
            }
            for (auto &x : prime) {
                if (1LL * i * x > N) break;
                vis[i * x] = x;
                if (i % x == 0) {
                    mob[i * x] = 0;
                    break;
                }
                mob[i * x] = -mob[i];
            }


        }
        for (int i = 1 ; i <= N ; i++) {
            mob[i] += mob[i - 1];
        }
    }
} // MobiusSieve
int main() {
    MobiusSieve::init(50005);
    using MobiusSieve::mob;
    auto get = [&](int x, int y) {
        int res = 0, k = min(x, y);
        for (int i = 1, R ; i <= k ; i = R + 1) {
            R = min(x / (x / i), y / (y / i));
            res += (mob[R] - mob[i - 1]) * (x / i) * (y / i);
        }
        return res;
    };
    int n;
    cin >> n;
    while (n--) {
        int a, b, c, d, k;
        cin >> a >> b >> c >> d >> k;
        int ans = get(b / k, d / k) - get((a - 1) / k, d / k) - get(b / k, (c - 1) / k) + get((a - 1) / k, (c - 1) / k);
        cout << ans << "\n";
    }
    return 0;
}

P3327 [SDOI2015] 约数个数和 - 洛谷

\[ \begin{align} d(i*j)=\sum_{x|i}\sum_{y|j}[\gcd(i,j)=1] \end{align} \]
\[ \begin{align} \sum_{i=1}^n\sum_{j=1}^md(i*j)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(i,j)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor*\lfloor\frac{m}{j}\rfloor*[\gcd(i,j)=1] \end{align} \]

令 \(f(x)=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor*\lfloor\frac{m}{j}\rfloor*[\gcd(i,j)=x]\)

\[ \begin{align} g(x)&=\sum_{x|d}f(d)\\ &=\sum_{x|d}\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor*\lfloor\frac{m}{j}\rfloor*[\gcd(i,j)=x]\\ &=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor*\lfloor\frac{m}{j}\rfloor*[x|\gcd(i,j)]\\ &=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{n}{i*x}\rfloor*\lfloor\frac{m}{j*x}\rfloor\\ &=\left(\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\lfloor\frac{n}{i*x}\rfloor\right)*\left(\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{m}{j*x}\rfloor\right)\\ \end{align} \]
\[ \begin{align} f(x)&=\sum_{x|d}\mu(\frac{d}{x})*g(d)\\ f(1)&=\sum_{1|d}\mu(\frac{d}{1})*g(d)\\ &=\sum_{d=0}^{\min(n,m)}\mu(d)*\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{i*d}\rfloor\right)*\left(\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{j*d}\rfloor\right)\\\\ \end{align} \]
代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
namespace MobiusSieve {
    vector<int> prime;
    vector<int> vis;
    vector<int> mob;
    void init(const int N) {
        prime.resize(0);
        vis.resize(0);
        vis.resize(N + 1);
        mob.resize(0);
        mob.resize(N + 1);
        mob[1] = 1;
        for (int i = 2 ; i <= N ; i++) {
            if (vis[i] == 0) {
                vis[i] = i;
                prime.push_back(i);
                mob[i] = -1;
            }
            for (auto &x : prime) {
                if (1LL * i * x > N) break;
                vis[i * x] = x;
                if (i % x == 0) {
                    mob[i * x] = 0;
                    break;
                }
                mob[i * x] = -mob[i];
            }
        }
        for (int i = 1 ; i <= N ; i++) {
            mob[i] += mob[i - 1];
        }
    }
} // MobiusSieve
i64 g[50005];
using MobiusSieve::mob;
void solve() {
    int n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    i64 ans = 0;
    for (int L = 1, R ; L <= n ; L = R + 1) {
        R = min(n / (n / L), m / (m / L));
        ans += 1LL * (mob[R] - mob[L - 1]) * g[n / L] * g[m / L];
    }
    cout << ans << "\n";
}
int main() {
    MobiusSieve::init(50000);
    for (int x = 1 ; x <= 50000 ; x++) {
        for (int L = 1, R ; L <= x ; L = R + 1) {
            R = x / (x / L);
            g[x] += 1LL * (R - L + 1) * (x / L);
        }
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

欧拉反演

\[ n=id_1(n)=\sum_{d\mid n}\varphi(d)*I(\frac{n}{d})=\sum_{d\mid n}\varphi(d) \]
例题

P1447 [NOI2010] 能量采集 - 洛谷

已知 \(n,m\), 求 \(\sum_{i=1}^n\sum_{j=1}^m(2*\gcd(i,j)-1)\)

\(ans=\sum_{i=1}^n\sum_{j=1}^m(2*\gcd(i,j)-1)=2*\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\)

根据欧拉反演可得 \(\gcd(i,j)=\sum_{d\mid \gcd(i,j)}\varphi(d)\)

\[ \begin{align} f&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\varphi(d)\\ &=\sum_{d=1}^n(\varphi(d)*\sum_{i=1}^n\sum_{j=1}^m[d\mid i\wedge d\mid j])\\ &=\sum_{d=1}^n(\varphi(d)*\sum_{i=1}^n[d|i]*\sum_{j=1}^m[d\mid j]))\\ &=\sum_{d=1}^n(\varphi(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor) \end{align} \]

除数反演

\[ \sigma_k=\sum_{d\mid n}d^k \]
例题

P3935 Calculating - 洛谷

已知 \(L,R\), 求 \(\sum_{i=L}^R\sigma_0(i)\)

令 \(S(n)=\sum_{i=1}^n\sigma_0(i)\), 则 \(ans=S(R)-S(L-1)\)

\[ \begin{align} S(n)&=\sum_{i=1}^n\sigma(i)\\ &=\sum_{i=1}^n\sum_{d\mid n}d^0\\ &=\sum_{d=1}^n\sum_{i=1}^n[d\mid i]\\ &=\sum_{d=1}\lfloor\frac{n}{d}\rfloor \end{align} \]