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

Wiki › Thuật toán › Toán học

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

huunguyen · Last updated 8, Tháng 4, 2026, 16:19

Hàm nhân tính $f$ thỏa $f (m n) = f (m) f (n)$ với $gcd (m, n) = 1$ . Sàng tuyến tính tính mọi giá trị hàm nhân tính đến $N$ trong $O (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ố nguyên tố cùng nhau với $n$ trong $[1, n]$	$ϕ (6) = 2$
Möbius	$μ (n)$	$(- 1)^{k}$ nếu $n$ tích $k$ SNT phân biệt, 0 nếu có $p^{2} ∣ n$	$μ (6) = 1$
Số ước	$d (n)$	Số ước dương của $n$	$d (6) = 4$
Tổng ước	$σ (n)$	Tổng ước dương của $n$	$σ (6) = 12$
Hàm đơn vị	$ε (n)$	$[n = 1]$	—
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}}$ :

$ϕ (n) = n \prod (1 - 1 / p_{i})$
$μ (n) = (- 1)^{k}$ nếu tất cả $a_{i} = 1$ , ngược lại $μ (n) = 0$
$d (n) = \prod (a_{i} + 1)$
$σ (n) = \prod \frac{p_{i}^{a_{i} + 1} - 1}{p_{i} - 1}$

Sàng tuyến tính — $O (N)$

Sàng Eratosthenes chuẩn là $O (N \log \log N)$ . Sàng tuyến tính đảm bảo mỗi số hợp bị loại đúng 1 lần:

const int MAXN = 1e7 + 5;
int phi[MAXN], mu[MAXN], lp[MAXN];   // lp[i] = smallest prime factor
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]) {
            primes.push_back(i);
            lp[i] = i;
            phi[i] = i - 1;       // i nguyên tố: phi = i-1
            mu[i] = -1;           // i nguyên tố: mu = -1
        }
        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;
            if (i % p == 0) {
                // p là ước nguyên tố nhỏ nhất của i
                phi[i * p] = phi[i] * p;
                mu[i * p] = 0;    // i*p có p^2 => mu = 0
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
                mu[i * p] = -mu[i];
            }
        }
    }
}

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

Tích Dirichlet: $(f * g) (n) = \sum_{d ∣ n} f (d) g (n / d)$

Quan hệ quan trọng: $f = g * 1$ tương đương $g = f * μ$ (inversion):

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

Ví dụ: $ϕ * 1 = id$ (tức là $\sum_{d ∣ n} ϕ (d) = n$ ).

Nghịch đảo Möbius trên tập hợp (SOS)

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

// Tính g từ f bằng Möbius inversion
// f[i] = sum_{j: i|j, j<=n} g[j]  =>  g[i] = sum_{j: i|j} mu[j/i] * f[j]
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)
            g[i] += mu[j/i] * f[j];
    return g;
}

Ứng dụng: Đếm cặp GCD

Đếm số cặp $(i, j)$ với $1 \leq i \leq j \leq n$ có $gcd (i, j) = k$ :

ans (k) = \sum_{i = 1}^{⌊ n / k ⌋} \sum_{j = i}^{⌊ n / k ⌋} [gcd (i, j) = 1] = \sum_{d = 1}^{⌊ n / k ⌋} μ (d) ⌊ n / (k d) ⌋^{2} / something

// Đế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;
        ans += mu[d] * cnt * (cnt - 1) / 2;
    }
    return ans;
}

Ứng dụng: Tổng phi Euler

$\sum_{i = 1}^{n} ϕ (i)$ bằng sàng: tính trực tiếp $O (N)$ . Dùng công thức $\sum_{d ∣ n} ϕ (d) = n$ để tính $O (\sqrt{N})$ :

// Tính sum phi(i) cho i=1..n trong O(sqrt(n)) bằng Dirichlet hyperbola
// Dùng f(n) = n*(n+1)/2, f = phi * 1, inversion: phi = f * mu

Khi nào dùng?

Bài toán đếm với điều kiện GCD — dùng Möbius inversion.
Tính hàm nhân tính đến $N$ lớn — dùng sàng tuyến tính.
$ϕ (n)$ trong bài toán modular inverse, Euler's theorem ( $a^{ϕ (n)} \equiv 1$ ).

Bình luận

Không có bình luận tại thời điểm này.