Hàm nhân tính và hàm Möbius

Mức độ: Chuyên sâu

Số ước, tổng các ước, hàm Euler φ đều có chung một tính chất: biết giá trị tại từng lũy thừa p^e thì nhân lại là ra giá trị tại n. Các hàm như vậy gọi là hàm nhân tính. Bài này học cách tính chúng cho một số và cho mọi số đến N (sàng tuyến tính), rồi học hàm Möbius μ, công cụ mạnh nhất để đếm các cặp, bộ số có ƯCLN bằng 1.

Các bạn cần nắm vững bài Số nguyên tố, Sàng Eratosthenes, Nguyên lý bù trừ và Hàm Euler.

Hàm nhân tính

Hàm f gọi là nhân tính nếu f(1) = 1 và f(a × b) = f(a) × f(b) mỗi khi ƯCLN(a, b) = 1.

Khi đó, với n = p₁^e₁ × … × p_r^e_r, ta có f(n) = f(p₁^e₁) × … × f(p_r^e_r). Chỉ cần biết f tại lũy thừa của số nguyên tố:

Hàm	Ý nghĩa	f(p^e)	Ví dụ n = 12 = 2² × 3
d(n)	số ước	e + 1	3 × 2 = 6
σ(n)	tổng các ước	1 + p + … + p^e	7 × 4 = 28
φ(n)	số nguyên tố cùng nhau với n	p^e - p^{e - 1}	2 × 2 = 4
μ(n)	hàm Möbius	-1 nếu e = 1, 0 nếu e ≥ 2	0 × (-1) = 0

Lý do d(n) nhân tính: mỗi ước của n chọn số mũ của p₁ từ 0 đến e₁ (có e₁ + 1 cách), số mũ của p₂ từ 0 đến e₂, … độc lập với nhau.

Lưu ý: “nhân tính” chỉ đòi hỏi khi a, b nguyên tố cùng nhau. d(4) = 3 nhưng d(2) × d(2) = 4.

Sàng tuyến tính

Sàng Eratosthenes gạch một số nhiều lần (12 bị gạch bởi 2 và 3). Sàng tuyến tính sắp xếp để mỗi hợp số n chỉ được tạo ra đúng một lần, từ n = i × p với p là ước nguyên tố nhỏ nhất của n:

Duyệt i từ 2 đến N, nếu i chưa được đánh dấu thì i là số nguyên tố, thêm vào danh sách.
Với mỗi số nguyên tố p trong danh sách (từ nhỏ đến lớn), đánh dấu i × p. Dừng ngay sau khi gặp p chia hết i, vì với các số nguyên tố lớn hơn, ước nguyên tố nhỏ nhất của i × p là p (của i), không phải số nguyên tố đang xét.

Vì mỗi số được tạo đúng một lần nên tổng số bước là N. Trong lúc tạo i × p, tính luôn hàm nhân tính:

p không chia hết i: ƯCLN(i, p) = 1 nên f(i × p) = f(i) × f(p).
p chia hết i: cần biết thêm số mũ của p trong i (hoặc phần p^e của i) để cập nhật.

Python
C++

def sang_tuyen_tinh(N):
    """Trả về (danh sách số nguyên tố, μ, φ) cho mọi số đến N."""
    mu, ph = [0] * (N + 1), [0] * (N + 1)
    mu[1] = ph[1] = 1
    la_hop_so = [False] * (N + 1)
    nt = []
    for i in range(2, N + 1):
        if not la_hop_so[i]:
            nt.append(i)
            mu[i], ph[i] = -1, i - 1
        for p in nt:
            if i * p > N:
                break
            la_hop_so[i * p] = True
            if i % p == 0:              # p là ước nguyên tố nhỏ nhất của i
                mu[i * p] = 0
                ph[i * p] = ph[i] * p
                break
            mu[i * p] = -mu[i]
            ph[i * p] = ph[i] * (p - 1)
    return nt, mu, ph

nt, mu, ph = sang_tuyen_tinh(12)
print(mu[1:])   # [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
print(ph[1:])   # [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N = 12;
    vector<int> mu(N + 1, 0), ph(N + 1, 0), nt;
    vector<bool> laHopSo(N + 1, false);
    mu[1] = ph[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!laHopSo[i]) {
            nt.push_back(i);
            mu[i] = -1;
            ph[i] = i - 1;
        }
        for (int p : nt) {
            if ((long long)i * p > N) break;
            laHopSo[i * p] = true;
            if (i % p == 0) {           // p là ước nguyên tố nhỏ nhất của i
                mu[i * p] = 0;
                ph[i * p] = ph[i] * p;
                break;
            }
            mu[i * p] = -mu[i];
            ph[i * p] = ph[i] * (p - 1);
        }
    }
    for (int i = 1; i <= N; i++) cout << mu[i] << " ";
    cout << endl;
    return 0;
}

Trong thực tế, sàng kiểu Eratosthenes (đổi dấu μ ở mọi bội của p, gán 0 ở mọi bội của p²) mất N × log log N bước, chậm hơn không đáng kể. Sàng tuyến tính đáng dùng khi cần tính một hàm nhân tính phức tạp, hoặc cần cả danh sách ước nguyên tố nhỏ nhất.

Hàm Möbius

μ(1) = 1; μ(n) = 0 nếu n chia hết cho bình phương của một số nguyên tố; còn lại μ(n) = (-1)^k với k là số ước nguyên tố của n.

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

Tính chất quan trọng nhất:

Tổng μ(d) trên mọi ước d của n bằng 1 nếu n = 1, bằng 0 nếu n lớn hơn 1.

Ví dụ n = 12: μ(1) + μ(2) + μ(3) + μ(4) + μ(6) + μ(12) = 1 - 1 - 1 + 0 + 1 + 0 = 0.

Lý do: chỉ các ước không có thừa số bình phương đóng góp. Nếu n có r ước nguyên tố khác nhau thì các ước đó ứng với tập con của r số nguyên tố, tập con k phần tử góp (-1)^k. Tổng là (1 - 1)^r = 0 khi r ≥ 1.

Đếm cặp có ƯCLN bằng 1

Nhờ tính chất trên, điều kiện “ƯCLN(x, y) = 1” viết được thành tổng:

[ƯCLN(x, y) = 1] = tổng μ(d) trên các d là ước chung của x và y.

Cộng trên mọi cặp x ≤ N, y ≤ M rồi đổi thứ tự cộng (với mỗi d, đếm số cặp có cả x, y chia hết cho d):

Số cặp nguyên tố cùng nhau = tổng μ(d) × (N // d) × (M // d).

Ví dụ N = M = 4: 16 - 4 - 1 + 0 = 11 (bỏ các cặp cùng chẵn, cùng chia hết cho 3).

Đây chính là nguyên lý bù trừ trên các số nguyên tố, viết gọn: μ(d) = 1 thì cộng, -1 thì trừ, 0 thì bỏ qua (d có ước bình phương thì đã được xử lý qua các số nguyên tố của nó).

Cùng một kỹ thuật cho rất nhiều bài:

Đếm	Công thức
cặp (x, y) có ƯCLN = k	thay N, M bằng N // k, M // k
bộ ba (x, y, z) có ƯCLN = 1	tổng μ(d) × (N // d)³
tập con của một mảng có ƯCLN = 1	tổng μ(d) × (2^c(d) - 1), c(d) = số phần tử chia hết cho d
số không có ước chính phương ≤ N	tổng μ(d) × (N // d²), d ≤ √N
tổng ƯCLN(x, y)	tổng φ(d) × (N // d) × (M // d)

Dòng cuối dùng φ thay μ, vì tổng φ(d) trên các ước d của n bằng n (bài Hàm Euler).

Lưu ý: các tổng trên có N số hạng. Khi N tới 10¹⁰ hoặc phải trả lời rất nhiều câu hỏi, cần thêm kỹ thuật chia khối: (N // d) chỉ nhận khoảng 2√N giá trị khác nhau, gom các d cùng giá trị lại. Đó là nội dung của bài tiếp theo.

Luyện tập

Gồm 22 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hàm nhân tính của một số

Bài 1. Số ước và tổng các ước

Nhập n (1 ≤ n ≤ 10¹²). In ra số ước dương của n và tổng các ước dương của n.

Ví dụ: nhập 12 thì in ra 6 28.

Kiểm tra: nhập 963761198400.

Xem đáp số

6720 5531765944320

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Tích các ước

Nhập n (1 ≤ n ≤ 10¹²). In ra tích tất cả các ước dương của n, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 12 thì in ra 1728.

Kiểm tra: nhập 963761198400.

Xem đáp số

390407607

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Hàm Möbius của một số

Nhập n (1 ≤ n ≤ 10¹²). In ra μ(n).

Ví dụ: nhập 30 thì in ra -1.

Kiểm tra: nhập 999999999999.

Xem đáp số

0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Số nhỏ nhất có đúng k ước

Nhập k (1 ≤ k ≤ 1000). In ra số nguyên dương nhỏ nhất có đúng k ước. Dữ liệu đảm bảo đáp số không vượt quá 10¹⁸.

Ví dụ: nhập 6 thì in ra 12.

Kiểm tra: nhập 1000.

Xem đáp số

810810000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Số dư thừa

Số n gọi là dư thừa nếu tổng các ước dương của n (kể cả n) lớn hơn 2n. Ví dụ 12 dư thừa vì 1 + 2 + 3 + 4 + 6 + 12 = 28 lớn hơn 24. Nhập N (1 ≤ N ≤ 10⁶). In ra số các số dư thừa từ 1 đến N.

Ví dụ: nhập 30 thì in ra 5.

Kiểm tra: nhập 1000000.

Xem đáp số

247545

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Sàng hàm nhân tính

Bài 6. Tổng các μ

Nhập N (1 ≤ N ≤ 10⁶). In ra μ(1) + μ(2) + … + μ(N).

Ví dụ: nhập 10 thì in ra -1.

Kiểm tra: nhập 1000000.

Xem đáp số

212

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Số không có ước chính phương

Một số gọi là không có ước chính phương nếu nó không chia hết cho p² với mọi số nguyên tố p (ví dụ 1, 2, 3, 5, 6, 7, 10, …). Nhập N (1 ≤ N ≤ 10¹²). In ra số các số như vậy từ 1 đến N.

Ví dụ: nhập 10 thì in ra 7.

Kiểm tra: nhập 1000000000000.

Xem đáp số

607927102274

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số thứ k không có ước chính phương

Nhập k (1 ≤ k ≤ 10¹⁰). In ra số thứ k (tính từ 1) trong dãy tăng dần các số không có ước chính phương 1, 2, 3, 5, 6, 7, 10, …

Ví dụ: nhập 7 thì in ra 10.

Kiểm tra: nhập 10000000000.

Xem đáp số

16449340709

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số có đúng 4 ước

Nhập N (1 ≤ N ≤ 10⁶). In ra số các số từ 1 đến N có đúng 4 ước dương.

Ví dụ: nhập 20 thì in ra 5.

Kiểm tra: nhập 1000000.

Xem đáp số

209892

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Số nhiều ước nhất

Nhập N (1 ≤ N ≤ 10⁶). In ra số nhỏ nhất từ 1 đến N có nhiều ước nhất, và số ước của nó.

Ví dụ: nhập 20 thì in ra 12 6.

Kiểm tra: nhập 1000000.

Xem đáp số

720720 240

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đếm cặp bằng hàm Möbius

Bài 11. Cặp nguyên tố cùng nhau trên hình chữ nhật

Nhập N, M (1 ≤ N, M ≤ 10⁶). In ra số cặp (x, y) với 1 ≤ x ≤ N, 1 ≤ y ≤ M và ƯCLN(x, y) = 1.

Ví dụ: nhập 3 4 thì in ra 9.

Kiểm tra: nhập 1000000 999999.

Xem đáp số

607926704783

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Cặp có ƯCLN bằng k

Nhập N, M, k (1 ≤ N, M, k ≤ 10⁶). In ra số cặp (x, y) với 1 ≤ x ≤ N, 1 ≤ y ≤ M và ƯCLN(x, y) = k.

Ví dụ: nhập 6 9 3 thì in ra 5.

Kiểm tra: nhập 1000000 1000000 7.

Xem đáp số

12406704135

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. ƯCLN là số nguyên tố trên hình chữ nhật

Nhập N, M (1 ≤ N, M ≤ 10⁶). In ra số cặp (x, y) với 1 ≤ x ≤ N, 1 ≤ y ≤ M mà ƯCLN(x, y) là một số nguyên tố.

Ví dụ: nhập 4 4 thì in ra 4.

Kiểm tra: nhập 1000000 1000000.

Xem đáp số

274934018418

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Bộ ba nguyên tố cùng nhau

Nhập N (1 ≤ N ≤ 10⁶). In ra số bộ ba có thứ tự (x, y, z) với 1 ≤ x, y, z ≤ N và ƯCLN(x, y, z) = 1.

Ví dụ: nhập 2 thì in ra 7.

Kiểm tra: nhập 1000000.

Xem đáp số

831907430687799769

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Nhìn từ góc khối lập phương

Các điểm nguyên (x, y, z) với 0 ≤ x, y, z ≤ N tạo thành một khối lập phương. Một người đứng ở gốc (0, 0, 0) nhìn ra. Điểm P (khác gốc) được nhìn thấy nếu trên đoạn thẳng từ gốc đến P không có điểm nguyên nào khác. Nhập N (1 ≤ N ≤ 10⁶). In ra số điểm nhìn thấy được.

Ví dụ: nhập 1 thì in ra 7.

Kiểm tra: nhập 1000000.

Xem đáp số

831909254469114121

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Tổng ƯCLN trên hình chữ nhật

Nhập N, M (1 ≤ N, M ≤ 10⁶). In ra tổng ƯCLN(x, y) với mọi 1 ≤ x ≤ N, 1 ≤ y ≤ M.

Ví dụ: nhập 3 4 thì in ra 16.

Kiểm tra: nhập 1000000 999999.

Xem đáp số

8643234647824

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 17. Dãy có ƯCLN bằng 1

Nhập N và k (1 ≤ N ≤ 10⁶, 1 ≤ k ≤ 10¹⁸). Đếm số dãy (a₁, …, a_k) với mỗi a_i từ 1 đến N và ƯCLN của cả dãy bằng 1. In ra kết quả mod 10⁹ + 7.

Ví dụ: nhập 3 2 thì in ra 7.

Kiểm tra: nhập 1000000 1000000000000000000.

Xem đáp số

548150192

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Tập con có ƯCLN bằng 1

Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau có n số a₁, …, a_n (1 ≤ a_i ≤ 10⁶). Đếm số tập con khác rỗng (chọn một số vị trí) có ƯCLN các phần tử bằng 1. In ra kết quả mod 10⁹ + 7.

Ví dụ:

Nhập	In ra
`3` `2 3 4`	`3`

Kiểm tra: nhập

10
6 10 15 4 9 25 49 35 21 1000000

Xem đáp số

962

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Cặp nguyên tố cùng nhau trong mảng

Dòng đầu là n (2 ≤ n ≤ 10⁵), dòng sau có n số a₁, …, a_n (1 ≤ a_i ≤ 10⁶). In ra số cặp chỉ số i nhỏ hơn j mà ƯCLN(a_i, a_j) = 1.

Ví dụ:

Nhập	In ra
`4` `2 3 4 5`	`5`

Kiểm tra: nhập

10
6 10 15 4 9 25 49 35 21 1000000

Xem đáp số

21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Tổng ước là số lẻ

Nhập N (1 ≤ N ≤ 10¹⁸). Đếm số các số n từ 1 đến N có tổng các ước dương σ(n) là số lẻ.

Ví dụ: nhập 10 thì in ra 5.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

1707106781

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Số ước của n!

Nhập n (1 ≤ n ≤ 10⁶). In ra số ước dương của n!, lấy dư cho 10⁹ + 7.

Ví dụ: nhập 5 thì in ra 16.

Kiểm tra: nhập 1000000.

Xem đáp số

141694778

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Ước chung là số chính phương

Nhập a, b (1 ≤ a, b ≤ 10¹²). In ra số các số chính phương (1, 4, 9, …) là ước chung của a và b.

Ví dụ: nhập 72 108 thì in ra 4.

Kiểm tra: nhập 1000000000000 999999000000.

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English