Hàm Möbius & Hàm Nhân Tính

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms - Möbius Function, Multiplicative Functions

---

Bản chất vấn đề

Hàm Mobius

Cho số nguyên dương \(n\). Hàm Mobius \(\mu(n)\) được dùng trong nguyên lý bao hàm - loại trừ trên ước số, giúp đếm số phần tử thỏa mãn điều kiện liên quan đến chia hết.

Ứng dụng chính: \(\sum_{d|n} \mu(d) = [n=1]\) — công thức nền tảng để loại bỏ đếm trùng.

Hàm nhân tính

Hàm \(f\) là nhân tính nếu \(\gcd(a,b)=1 \Rightarrow f(ab)=f(a) \cdot f(b)\). Hiểu tính chất nhân tính giúp tính nhanh nhiều hàm số học (Euler \(\varphi\), Mobius \(\mu\), số ước \(\sigma_0\), tổng ước \(\sigma_1\)).

---

1. Hàm Mobius

Định nghĩa

Hàm Mobius \(\mu(n)\):

\[\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n = p_1 p_2 \cdots p_k \text{ (tích các số nguyên tố phân biệt)} \\ 0 & \text{if } n \text{ chia hết cho bình phương số nguyên tố} \end{cases}\]

Bảng giá trị

\(n\)	1	2	3	4	5	6	7	8	9	10	12
\(\mu(n)\)	1	-1	-1	0	-1	1	-1	0	0	1	0

\(\mu(4) = 0\) vì \(4 = 2^2\) (chia hết cho bình phương).

\(\mu(6) = 1\) vì \(6 = 2 \cdot 3\) (\(k=2\) cặp, \((-1)^2 = 1\)).

Biểu đồ giá trị của hàm Möbius \(\mu(n)\):

Ứng dụng: Nghịch đảo Dirichlet

\[\sum_{d | n} \mu(d) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases}\]

Hệ quả (nguyên lý bao hàm - loại trừ):

\[[n = 1] = \sum_{d | n} \mu(d)\]

Tính \(\mu(n)\) bằng sàng

C++Python

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> mu(n + 1, 1);
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    mu[1] = 1;                          // μ(1) = 1
    for (int i = 2; i <= n; i++) {      // duyệt các số từ 2 đến n
        if (is_prime[i]) {
            primes.push_back(i);        // i là số nguyên tố
            mu[i] = -1;                 // μ(i) = -1 (1 thừa số nguyên tố)
        }
        for (int p : primes) {          // duyệt qua các số nguyên tố đã tìm được
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {           // p² | (i*p) → μ = 0
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];     // nhân thêm thừa số nguyên tố phân biệt
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << "mu(" << i << ") = " << mu[i] << "\n";
    return 0;
}

n = int(input())
mu = [1] * (n + 1)
is_prime = [True] * (n + 1)
primes = []

mu[1] = 1                          # μ(1) = 1
for i in range(2, n + 1):          # duyệt các số từ 2 đến n
    if is_prime[i]:
        primes.append(i)           # i là số nguyên tố
        mu[i] = -1                 # μ(i) = -1
    for p in primes:               # duyệt qua các số nguyên tố đã tìm được
        if i * p > n:
            break
        is_prime[i * p] = False
        if i % p == 0:             # p² | (i*p) → μ = 0
            mu[i * p] = 0
            break
        else:
            mu[i * p] = -mu[i]     # nhân thêm thừa số nguyên tố phân biệt

for i in range(1, n + 1):
    print(f"mu({i}) = {mu[i]}")

---

2. Hàm Nhân Tính (Multiplicative Function)

Định nghĩa

Hàm \(f\) là nhân tính nếu \(\gcd(a, b) = 1 \Rightarrow f(ab) = f(a) \cdot f(b)\).

Hàm \(f\) là hoàn toàn nhân tính nếu \(f(ab) = f(a) \cdot f(b)\) với mọi \(a, b\).

Các hàm nhân tính quan trọng

Hàm	Định nghĩa	Nhân tính?
\(\varphi(n)\) (Euler)	Số nguyên tố cùng nhau	Có
\(\mu(n)\) (Mobius)	Hàm Mobius	Có
\(\sigma_0(n)\)	Số ước	Có
\(\sigma_1(n)\)	Tổng ước	Có
\(\text{id}(n) = n\)	Hàm đồng nhất	Hoàn toàn
\(\text{id}_k(n) = n^k\)	Lũy thừa	Hoàn toàn
\(\mathbf{1}(n) = 1\)	Hàm hằng	Hoàn toàn

Tính chất: Convolution Dirichlet

Nếu \(f, g\) là nhân tính thì \(f * g\) cũng là nhân tính, với:

\[(f * g)(n) = \sum_{d | n} f(d) \cdot g(n/d)\]

Ví dụ: \(\varphi * \mathbf{1} = \text{id}\), tức \(\sum_{d|n} \varphi(d) = n\).

---

3. Phân tích tính đúng đắn

Tại sao \(\sum_{d|n} \mu(d) = [n=1]\)?

Trường hợp \(n = 1\): \(\sum_{d|1} \mu(d) = \mu(1) = 1\). Đúng.

Trường hợp \(n > 1\): Viết \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\) với \(k \ge 1\).

Các ước \(d\) của \(n\) mà \(\mu(d) \neq 0\) là các tích phân biệt của \(p_1, p_2, \ldots, p_k\) (mỗi ước chọn hoặc không chọn mỗi \(p_i\)).

\[\sum_{d|n} \mu(d) = \sum_{S \subseteq \{p_1, \ldots, p_k\}} (-1)^{|S|} = \sum_{j=0}^{k} \binom{k}{j} (-1)^j = (1 - 1)^k = 0\]

Đây chính là khai triển nhị thức Newton của \((1-1)^k = 0\) với \(k \ge 1\).

Tại sao Mobius là hàm nhân tính?

Nếu \(\gcd(a, b) = 1\), thì \(ab\) có bình phương nguyên tố \(\iff\) \(a\) hoặc \(b\) có bình phương nguyên tố. Do đó \(\mu(ab) = \mu(a) \cdot \mu(b)\).

---

4. Đánh giá độ phức tạp

Thao tác	Thời gian
Sàng tính \(\mu\) hoặc \(\varphi\)	\(O(N \log \log N)\)
Linear sieve tính \(\mu\), \(\varphi\)	\(O(N)\)

---

Code minh họa: Sàng tuyến tính tính nhiều hàm cùng lúc

C++Python

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> mu(n + 1, 0), phi(n + 1, 0);
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    mu[1] = 1;                      // μ(1) = 1
    phi[1] = 1;                     // φ(1) = 1

    for (int i = 2; i <= n; i++) {  // duyệt các số từ 2 đến n
        if (is_prime[i]) {
            primes.push_back(i);    // i là số nguyên tố
            mu[i] = -1;             // μ(i) = -1
            phi[i] = i - 1;         // φ(i) = i - 1 (các số < i và nguyên tố cùng nhau)
        }
        for (int p : primes) {      // duyệt các số nguyên tố
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {       // p² | (i*p) → μ = 0, φ(i*p) = φ(i)*p
                mu[i * p] = 0;
                phi[i * p] = phi[i] * p;
                break;
            } else {                // p nguyên tố cùng nhau với i
                mu[i * p] = -mu[i];
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << i << ": mu=" << mu[i] << " phi=" << phi[i] << "\n";
    return 0;
}

n = int(input())
mu = [0] * (n + 1)
phi = [0] * (n + 1)
is_prime = [True] * (n + 1)
primes = []

mu[1] = phi[1] = 1

for i in range(2, n + 1):          # duyệt các số từ 2 đến n
    if is_prime[i]:
        primes.append(i)           # i là số nguyên tố
        mu[i] = -1                 # μ(i) = -1
        phi[i] = i - 1             # φ(i) = i - 1
    for p in primes:               # duyệt các số nguyên tố
        if i * p > n:
            break
        is_prime[i * p] = False
        if i % p == 0:             # p² | (i*p) → μ = 0, φ(i*p) = φ(i)*p
            mu[i * p] = 0
            phi[i * p] = phi[i] * p
            break
        else:                      # p nguyên tố cùng nhau với i
            mu[i * p] = -mu[i]
            phi[i * p] = phi[i] * (p - 1)

for i in range(1, n + 1):
    print(f"{i}: mu={mu[i]} phi={phi[i]}")

---

5. Bài tập luyện tập

Mã bài	Tên bài tập	Độ khó	Kiểu bài tập (Bản chất)	Bài học lý thuyết
mobius-basic	Hàm Möbius	⭐	Tính \(\mu(n)\)	Hàm Mobius & Hàm Nhân Tính
mobius-range	Sàng Möbius	⭐⭐	Sàng \(\mu(1..N)\)	Hàm Mobius & Hàm Nhân Tính
mobius-mult-func	Hàm nhân tính	⭐⭐	Hàm nhân tính \(\varphi\)	Hàm Mobius & Hàm Nhân Tính
mobius-sigma0	Tổng số ước	⭐	\(\sum \sigma_0(i)\)	Hàm Mobius & Hàm Nhân Tính
mobius-squarefree	Đếm số square-free	⭐⭐⭐	\(\sum \mu(i) \lfloor N/i^2 \rfloor\)	Hàm Mobius & Hàm Nhân Tính
mobius-coprime-cnt	Đếm cặp nguyên tố cùng nhau	⭐⭐⭐⭐	Möbius + Inclusion-Exclusion	Hàm Mobius & Hàm Nhân Tính
mobius-div-sum	Tổng GCD dùng Möbius	⭐⭐⭐⭐	\(\sum \gcd(i,j)\)	Hàm Mobius & Hàm Nhân Tính
mobius-triple	Đếm bộ gcd=1	⭐⭐⭐⭐	\(\sum \mu(d) \lfloor A/d \rfloor \lfloor B/d \rfloor \lfloor C/d \rfloor\)	Hàm Mobius & Hàm Nhân Tính

---

💬 Bình luận