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 đề

Bài toán động lực: Đếm cặp \((i, j)\) với \(\gcd(i, j) = 1\)

Cho \(A, B \le 10^6\) (ví dụ \(A = 5\), \(B = 4\)). Đếm số cặp \((i, j)\) với \(1 \le i \le A\), \(1 \le j \le B\) sao cho \(\gcd(i, j) = 1\).

Duyệt từng cặp rồi tính \(\gcd\) mất \(O(A \cdot B \log)\) — quá chậm với \(10^6 \times 10^6\).

Dùng tính chất \([\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d)\):

\[\text{Đáp án} = \sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{d \mid \gcd(i,j)} \mu(d) = \sum_{d=1}^{\min(A,B)} \mu(d) \cdot \Big\lfloor \frac{A}{d} \Big\rfloor \cdot \Big\lfloor \frac{B}{d} \Big\rfloor\]

Chỉ cần sàng \(\mu(1..10^6)\) một lần (\(O(N)\)), rồi tính tổng trên theo \(d\) (\(O(N)\)). Đây là lý do ta học hàm Möbius!

Kiểm tra tay với \(A = 3\), \(B = 2\): các cặp \((1,1), (1,2), (2,1), (3,1), (3,2)\) có gcd \(= 1\) → đáp án \(5\). Công thức: \(\mu(1)\cdot 3\cdot 2 + \mu(2)\cdot 1\cdot 1 = 1\cdot 6 + (-1)\cdot 1 = 5\). Đúng!

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]}")

Trace tay sàng linear tính \(\mu(1..10)\):

Bước	\(i\)	\(i\) nguyên tố?	\(p\) xét	\(i \times p\)	\(i \bmod p\)	Kết quả
1	2	Có → primes=[2], \(\mu(2)=-1\)	2	4	\(2 \bmod 2 = 0\) → \(\mu(4)=0\), break	\(\mu(4)=0\) (vì \(2^2 \mid 4\))
2	3	Có → primes=[2,3], \(\mu(3)=-1\)	2	6	\(3 \bmod 2 \ne 0\) → \(\mu(6)=-\mu(3)=1\)	\(\mu(6)=1\)
3	3	—	3	9	\(3 \bmod 3 = 0\) → \(\mu(9)=0\), break	\(\mu(9)=0\) (vì \(3^2 \mid 9\))
4	4	Không (\(\mu(4)=0\))	2	8	\(4 \bmod 2 = 0\) → \(\mu(8)=0\), break	\(\mu(8)=0\) (vì \(2^2 \mid 8\))
5	5	Có → \(\mu(5)=-1\)	2	10	\(5 \bmod 2 \ne 0\) → \(\mu(10)=-\mu(5)=1\)	\(\mu(10)=1\) (\(10=2\cdot 5\))
6	6	Không (\(\mu(6)=1\))	2	12 \(> 10\) → dừng	—	—
7	7	Có → \(\mu(7)=-1\)	2	14 \(> 10\) → dừng	—	—

Kết quả: \(\mu = [1, -1, -1, 0, -1, 1, -1, 0, 0, 1]\) cho \(n = 1..10\). Quy luật: gặp \(p^2 \mid (i \cdot p)\) thì gán \(0\) và break ngay (mỗi hợp số chỉ bị sàng bởi nguyên tố nhỏ nhất của nó).

---

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\).

Ví dụ số với \(n = 6\): ước của \(6\) là \(1, 2, 3, 6\). \(\varphi(1) + \varphi(2) + \varphi(3) + \varphi(6) = 1 + 1 + 2 + 2 = 6\). Đúng!

Ví dụ số với Möbius: \((\mu * \mathbf{1})(6) = \mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 + (-1) + (-1) + 1 = 0 = [6 = 1]\) (sai → bằng 0). Đúng với công thức nghịch đảo!

---

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)\)

Lỗi thường gặp: SAI / ĐÚNG

Lỗi 1: Quên \(\mu(1) = 1\)

// SAI: khởi tạo mu toàn 0 rồi chỉ gán từ 2 → mu[1] = 0, mọi công thức đếm sai
vector<int> mu(n + 1, 0);

// ĐÚNG: mu[1] = 1 theo định nghĩa
mu[1] = 1;

Lỗi 2: Quên break khi \(p \mid i\)

Mỗi hợp số chỉ được sàng đúng một lần bởi nguyên tố nhỏ nhất của nó. Nếu không break, số đó bị ghi đè nhiều lần → \(\mu\) sai và mất tính tuyến tính \(O(N)\).

// SAI: không break → i*p bị xử lý bởi nhiều p
if (i % p == 0) {
    mu[i * p] = 0;
}  // thiếu break!

// ĐÚNG:
if (i % p == 0) {
    mu[i * p] = 0;
    break;  // p là nguyên tố nhỏ nhất của i*p, dừng ngay
}

Lỗi 3: Nhầm \(\mu(n) = 0\) với "không có ước"

\(\mu(n) = 0\) nghĩa là \(n\) chia hết cho bình phương nguyên tố (ví dụ \(4, 8, 9, 12\)), không phải \(n\) không có ước. Trong công thức đếm cặp gcd, số hạng \(\mu(d) = 0\) chỉ đơn giản bị bỏ qua.

---

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