Wiki › Thuật toán › Toán học › Hàm nhân tính và Sàng tuyến tính

Hàm nhân tính và Sàng tuyến tính

huunguyen Updated Tháng sáu 1, 2026

Một hàm nhân tính (multiplicative function) $f$ là hàm số học thỏa $f (1) = 1$ và $f (m n) = f (m) f (n)$ với mọi cặp $gcd (m, n) = 1$ . Các hàm như $ϕ$ (Euler), $μ$ (Möbius), $d$ (số ước), $σ$ (tổng ước) đều là hàm nhân tính. Sàng tuyến tính (linear sieve) cho phép tính toàn bộ giá trị của một hàm nhân tính trên đoạn $[1, N]$ trong $O (N)$ — nhanh hơn cả sàng Eratosthenes $O (N \log \log N)$ và nhanh hơn rất nhiều so với việc phân tích thừa số từng số ( $O (N \sqrt{N})$ ).

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

Hàm	Ký hiệu	Định nghĩa	Ví dụ
Phi Euler	$ϕ (n)$	Số phần tử trong $[1, n]$ nguyên tố cùng nhau với $n$	$ϕ (6) = 2$ (là $1, 5$ )
Möbius	$μ (n)$	$(- 1)^{k}$ nếu $n$ là tích $k$ SNT phân biệt, $0$ nếu có $p^{2} ∣ n$	$μ (6) = 1$ , $μ (12) = 0$
Số ước	$d (n)$	Số ước dương của $n$	$d (6) = 4$
Tổng ước	$σ (n)$	Tổng các ước dương của $n$	$σ (6) = 12$
Hàm đơn vị	$ε (n)$	$[n = 1]$ (bằng $1$ khi $n = 1$ , ngược lại $0$ )	—
Hàm hằng	$1 (n)$	$1$ với mọi $n$	—

Tính theo phân tích thừa số $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ (vì nhân tính nên chỉ cần biết giá trị trên các lũy thừa nguyên tố $p^{a}$ rồi nhân lại):

$ϕ (n) = n \prod_{i} (1 - \frac{1}{p_{i}})$
$μ (n) = (- 1)^{k}$ nếu mọi $a_{i} = 1$ , ngược lại $μ (n) = 0$
$d (n) = \prod_{i} (a_{i} + 1)$
$σ (n) = \prod_{i} \frac{p_{i}^{a_{i} + 1} - 1}{p_{i} - 1}$

Ý tưởng / Trực giác

Vì sao "nhân tính" lại quan trọng? Nếu biết $f$ trên các lũy thừa nguyên tố thì biết $f$ trên mọi số: tách $n$ thành tích các $p_{i}^{a_{i}}$ đôi một nguyên tố cùng nhau rồi nhân. Bài toán tính $f$ trên cả mảng quy về "làm sao gán đúng giá trị khi xây dần từng số".

Vì sao sàng tuyến tính chạy $O (N)$ ? Mấu chốt: ta muốn mỗi hợp số bị "đánh dấu loại" đúng một lần duy nhất. Sàng Eratosthenes loại $12$ nhiều lần (qua $2$ , qua $3$ ). Sàng tuyến tính quy ước: số hợp $x$ chỉ được sinh ra bởi $x = i \cdot p$ với $p$ là ước nguyên tố nhỏ nhất (smallest prime factor, lp) của $x$ . Vì mỗi $x$ có duy nhất một $lp (x)$ và một cách viết $x = (x / lp (x)) \cdot lp (x)$ , mỗi $x$ chỉ bị sinh một lần $\Rightarrow$ tổng công việc là $O (N)$ .

Vì sao cập nhật được $ϕ, μ$ ngay khi sinh? Khi sinh $x = i \cdot p$ ( $p$ là SNT đang xét, duyệt tăng dần), có hai trường hợp:

$p ∤ i$ ( $gcd (i, p) = 1$ ): khi đó $i$ và $p$ nguyên tố cùng nhau, dùng tính nhân tính trực tiếp: $ϕ (i p) = ϕ (i) ϕ (p) = ϕ (i) (p - 1)$ , $μ (i p) = μ (i) μ (p) = - μ (i)$ .
$p ∣ i$ : $p$ đã là ước của $i$ , nên $i p$ chứa $p^{2}$ . Lúc này $μ (i p) = 0$ . Với phi: thêm một thừa số $p$ chỉ nhân thêm $p$ (không phải $p - 1$ ), tức $ϕ (i p) = ϕ (i) \cdot p$ . Quan trọng: ta break ngay sau trường hợp này, vì $p$ chính là $lp (i)$ nên các $p^{'} > p$ tiếp theo sẽ không còn là $lp$ của $i \cdot p^{'}$ — để chúng cho vòng lặp của $i^{'}$ khác xử lý, đảm bảo "loại đúng một lần".

Quy tắc nhân tính tổng quát: nếu $f (p^{a})$ tính được nhanh từ $f (p^{a - 1})$ , thì cùng khung sàng này tính được $d, σ$ ,... (chỉ cần thêm mảng đếm số mũ của $lp$ ).

Ví dụ chạy tay

Chạy sàng tuyến tính tính $ϕ$ và $μ$ tới $N = 12$ . Ký hiệu: primes là danh sách SNT đã tìm, dòng đánh dấu >> là bước đang sinh hợp số $i \cdot p$ .

i=2  : 2 là SNT  -> primes={2}        phi[2]=1   mu[2]=-1
       >> i*2=4  : p=2, 2|2 -> phi[4]=phi[2]*2=2,  mu[4]=0,  BREAK

i=3  : 3 là SNT  -> primes={2,3}      phi[3]=2   mu[3]=-1
       >> i*2=6  : p=2, 2∤3 -> phi[6]=phi[3]*(2-1)=2,  mu[6]=-mu[3]=1
       >> i*3=9  : p=3, 3|3 -> phi[9]=phi[3]*3=6,  mu[9]=0,  BREAK

i=4  : 4 hợp số (lp=2)                phi[4]=2   mu[4]=0
       >> i*2=8  : p=2, 2|4 -> phi[8]=phi[4]*2=4,  mu[8]=0,  BREAK

i=5  : 5 là SNT  -> primes={2,3,5}    phi[5]=4   mu[5]=-1
       >> i*2=10 : p=2, 2∤5 -> phi[10]=phi[5]*(2-1)=4, mu[10]=-mu[5]=1
       >> i*3=15 (>12, dừng vòng p vì 5*3=15>12)

i=6  : 6 hợp số (lp=2)                phi[6]=2   mu[6]=1
       >> i*2=12 : p=2, 2|6 -> phi[12]=phi[6]*2=4, mu[12]=0,  BREAK

Kết quả tích lũy (ô đang điền được làm dấu):

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

Kiểm chứng: $ϕ (12) = 12 (1 - \frac{1}{2}) (1 - \frac{1}{3}) = 4$ ✓; $12 = 2^{2} \cdot 3$ có $p^{2} \Rightarrow μ (12) = 0$ ✓.

Cài đặt

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

const int MAXN = 1e7 + 5;
int phi[MAXN], mu[MAXN], lp[MAXN];   // lp[i] = ước nguyên tố nhỏ nhất của i
vector<int> primes;
bool is_composite[MAXN];

void linear_sieve(int n) {
    phi[1] = mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {       // i là số nguyên tố
            primes.push_back(i);
            lp[i]  = i;
            phi[i] = i - 1;           // các số 1..i-1 đều coprime với SNT i
            mu[i]  = -1;              // 1 thừa số nguyên tố, mũ 1
        }
        // sinh các hợp số i*p với p <= lp[i], dừng khi vượt n
        for (int j = 0; j < (int)primes.size()
                        && (long long)i * primes[j] <= n; j++) {
            int p = primes[j];
            is_composite[i * p] = true;
            lp[i * p] = p;            // p là ƯCNT nhỏ nhất của i*p
            if (i % p == 0) {
                // p | i  => i*p chứa p^2
                phi[i * p] = phi[i] * p;   // thêm 1 thừa số p: nhân p
                mu[i * p]  = 0;            // có p^2 => mu = 0
                break;                     // dừng để mỗi hợp số bị sinh đúng 1 lần
            } else {
                // gcd(i, p) = 1 => dùng tính nhân tính
                phi[i * p] = phi[i] * (p - 1);
                mu[i * p]  = -mu[i];
            }
        }
    }
}

Khung sàng cho $d (n)$ và $σ (n)$ — cần thêm mảng số mũ của $lp$ :

int d[MAXN], cnt[MAXN];        // cnt[i] = số mũ của lp trong i
long long sigma[MAXN], pw[MAXN]; // pw[i] = lp^(cnt+1) hỗ trợ tính sigma

void sieve_d_sigma(int n) {
    d[1] = sigma[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            cnt[i] = 1;  d[i] = 2;               // p^1 có 2 ước
            pw[i]  = (long long)i * i;            // p^2
            sigma[i] = 1 + i;                     // 1 + p
        }
        for (int j = 0; j < (int)primes.size()
                        && (long long)i * primes[j] <= n; j++) {
            int p = primes[j], x = i * p;
            is_composite[x] = true;
            if (i % p == 0) {
                cnt[x] = cnt[i] + 1;
                d[x]   = d[i] / (cnt[i] + 1) * (cnt[x] + 1);  // (a+2)/(a+1)
                pw[x]  = pw[i] * p;
                sigma[x] = sigma[i] / (pw[i] - 1) * (pw[x] - 1);
                break;
            } else {
                cnt[x] = 1;  d[x] = d[i] * 2;     // nhân (1+1) cho thừa số p mới
                pw[x]  = (long long)p * p;
                sigma[x] = sigma[i] * (1 + p);
            }
        }
    }
}

Độ phức tạp

Thời gian: $O (N)$ . Lý do: vòng ngoài chạy $N$ lần; tổng số lần thực thi vòng trong bằng số hợp số được sinh, mà mỗi hợp số $x \leq N$ bị sinh đúng một lần (qua phân tích duy nhất $x = (x / lp) \cdot lp$ với điều kiện break). Vậy tổng công việc là $Θ (N)$ — không có thừa số $\log$ như Eratosthenes.
Bộ nhớ: $O (N)$ cho mỗi mảng (phi, mu, lp, is_composite...). Với $N = 10^{7}$ , mỗi mảng int chiếm $\approx 40$ MB; cân nhắc gộp/bỏ mảng không cần để khớp giới hạn bộ nhớ. Danh sách primes có $O (N / \ln N)$ phần tử.

⚠️ Lỗi thường gặp

Tràn số khi nhân chỉ số: điều kiện i * primes[j] <= n phải ép (long long), nếu không $i \cdot p$ tràn int (với $N ~ 10^{7}$ , tích có thể $~ 10^{14}$ ) gây sai biên hoặc vòng lặp vô tận.
Quên break khi i % p == 0: đây là lỗi phá vỡ tính tuyến tính. Bỏ break khiến hợp số bị sinh nhiều lần, giá trị $ϕ / μ$ bị ghi đè sai và độ phức tạp tụt về $O (N \log \log N)$ (hoặc tệ hơn).
Modulo âm với $μ$ : $μ$ nhận giá trị $- 1$ . Khi cộng dồn $\sum μ (d) \cdot (\dots)$ theo modulo, kết quả có thể âm — phải ((x % MOD) + MOD) % MOD trước khi in, nếu không ra số âm sai.
Nghịch đảo trong công thức $σ, d$ dưới modulo: công thức $d [x] = d [i] / (c n t + 1) \cdot (c n t + 2)$ và $σ$ chia $(p^{k} - 1)$ chỉ đúng với số nguyên thật. Nếu làm theo modulo $10^{9} + 7$ , phép chia phải thay bằng nghịch đảo modular (Fermat), và chỉ hợp lệ khi mẫu nguyên tố cùng nhau với MOD — chia trực tiếp sẽ sai.
Quên khởi tạo $f (1) = 1$ : mọi hàm nhân tính có $f (1) = 1$ . Bỏ sót làm hỏng mọi giá trị nhân lên từ $1$ .
Cận trên sai khi $N = 1$ : với $N = 1$ vòng sàng không chạy; phải đảm bảo $f [1]$ đã gán đúng trước khi dùng.

Tích Dirichlet và Nghịch đảo Möbius

Tích Dirichlet: $(f * g) (n) = \sum_{d ∣ n} f (d) g (n / d)$ . Tích của hai hàm nhân tính lại là hàm nhân tính.

Quan hệ then chốt (nghịch đảo Möbius):

$g (n) = \sum_{d ∣ n} f (d) ⟺ f (n) = \sum_{d ∣ n} μ (d) g (n / d)$

Ví dụ kinh điển: $ϕ * 1 = id$ , tức $\sum_{d ∣ n} ϕ (d) = n$ . Dạng đảo của nó dùng $μ$ để "gỡ" tổng ước số — nền tảng của các bài đếm theo điều kiện $gcd$ .

// Tính g từ f bằng nghịch đảo Möbius: g(n) = sum_{d|n} mu(n/d) f(d)
vector<long long> mobius_inversion(vector<long long>& f, int n) {
    vector<long long> g(n + 1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)   // j chạy qua các bội của i
            g[i] += mu[j / i] * f[j];
    return g;
}

Ứng dụng: Đếm cặp nguyên tố cùng nhau

Đếm số cặp $(i, j)$ , $1 \leq i < j \leq n$ , có $gcd (i, j) = 1$ . Dùng $μ$ để khử điều kiện $gcd$ : số cặp có $gcd$ chia hết cho $d$ là $(\binom{⌊ n / d ⌋}{2})$ , nghịch đảo Möbius cho:

// Đếm cặp (i,j), 1<=i<j<=n, gcd(i,j)=1
long long count_coprime_pairs(int n) {
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        long long cnt = n / d;                 // số bội của d trong [1,n]
        ans += (long long)mu[d] * cnt * (cnt - 1) / 2;  // mu[d] * C(cnt,2)
    }
    return ans;
}

Khi nào dùng?

Bài toán đếm với điều kiện $gcd$ — dùng nghịch đảo Möbius để khử ràng buộc.
Tính một hàm nhân tính trên cả $[1, N]$ với $N$ lớn — dùng sàng tuyến tính $O (N)$ .
$ϕ (n)$ trong nghịch đảo modular và định lý Euler ( $a^{ϕ (n)} \equiv 1 (\mod n)$ khi $gcd (a, n) = 1$ ).
Đếm cấu hình bất biến qua phép xoay (vòng cổ, vòng tròn) — công thức Burnside dùng $ϕ$ trên các ước của $n$ .

Bài tập luyện

Đếm số lượng ước (cntdivs) — (Amateur) Sàng tính $d (n)$ cho mọi $n \leq 10^{6}$ một lần để trả lời nhiều truy vấn — bài nhập môn dùng khung sàng cho hàm nhân tính.
Bội số nguyên tố (primemult) — (Intermediate) Đếm số trong $[1, n]$ chia hết cho ít nhất một SNT cho trước bằng bao hàm–loại trừ (dấu $(- 1)^{k + 1}$ chính là tinh thần $μ$ ).
Phân tích ước số (divanal) — (Intermediate) Tính $d$ , $σ$ và tích các ước trực tiếp từ phân tích thừa số nguyên tố — áp dụng đúng các công thức nhân tính (kèm nghịch đảo modular).
Tổng các ước số (sumdivs) — (Advanced) Tính $\sum_{i = 1}^{n} σ (i)$ với $n \leq 10^{12}$ bằng kỹ thuật tổng theo khối (divisor block sum) trên hàm nhân tính $σ$ .
Đếm cặp nguyên tố cùng nhau (cntcopair) — (Advanced) Đếm cặp $gcd = 1$ trong mảng — áp dụng trực tiếp nghịch đảo Möbius như mục ứng dụng ở trên.
Đếm vòng cổ (cntnecklace) — (Advanced) Đếm chuỗi $n$ hạt $m$ màu bất biến qua phép xoay — công thức $\frac{1}{n} \sum_{d ∣ n} ϕ (d) m^{n / d}$ dùng hàm Euler trên các ước.