Các Định Nghĩa Cơ Bản

Trước tiên, ta định nghĩa tích chập Dirichlet như sau: cho hai hàm số học $f$ và $g$, tích chập được ký hiệu là $(f * g)(n) = \sum_{d \mid n} f(d)g\left(\frac{n}{d}\right)$.

Tiếp theo, ta định nghĩa hàm nhân tính $f$: với mọi $a, b$ thỏa mãn $\gcd(a, b) = 1$, ta có $f(ab) = f(a)f(b)$.

Hàm Möbius $\mu$

Cho một số nguyên dương $n$ có dạng phân tích thừa số nguyên tố $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, hàm Möbius được định nghĩa:

$$\mu(n) = \begin{cases} 1 & \text{nếu } n = 1 \ 0 & \text{nếu tồn tại } a_i \ge 2 \ (-1)^k & \text{trong các trường hợp còn lại} \end{cases}$$

Dựa trên định nghĩa hàm nhân tính, dễ dàng nhận thấy $\mu$ là một hàm nhân tính.

Hàm Euler $\varphi$

Hàm $\varphi(n)$ đếm số lượng các số nguyên trong khoảng $1$ đến $n$ nguyên tố cùng nhau với $n$. Để chứng minh tính chất nhân tính của $\varphi$, ta xây dựng một ma trận $n \times m$ với $n \perp m$:

• Hàng thứ $i$, cột thứ $j$ chứa giá trị $(i-1)m + j$
• Ma trận này chứa đầy đủ các số từ $1$ đến $nm$

Xét mỗi cột: do $\gcd(im + j, m) = \gcd(j, m)$, một cột hoàn toàn nguyên tố cùng nhau với $m$ hoặc không có số nào như vậy. Số cột nguyên tố cùng với $m$ là $\varphi(m)$.

Xét mỗi hàng: do $\gcd(n, m) = 1$, các giá trị trong mỗi hàng $im + j$ tạo thành một hệ thặng dư đầy đủ modulo $n$. Số hàng nguyên tố cùng với $n$ là $\varphi(n)$.

Từ đó suy ra $\varphi(nm) = \varphi(n)\varphi(m)$, chứng minh $\varphi$ là hàm nhân tính.

Công thức trực tiếp để tính $\varphi(n)$ với $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$:

$$\varphi(n) = n\prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right)$$

Chứng minh dựa trên tính nhân tính: $\varphi(n) = \prod_{i=1}^{k}\varphi(p_i^{a_i})$, và đặc biệt $\varphi(p^k) = p^k\left(1 - \frac{1}{p}\right)$.

Sàng Tuyến Tính

Việc tính $\mu(n)$ và $\varphi(n)$ bằng cách phân tích thừa số nguyên tố có độ phức tạp $O(\sqrt{n})$, khá kém hiệu quả khi cần tính nhiều giá trị. Sàng tuyến tính (linear sieve) là giải pháp tối ưu hơn.

Khi sàng các số nguyên tố bằng phương pháp tuyến tính, ta sử dụng $i \times p_j$ để loại bỏ hợp số. Chú ý rằng nếu $\gcd(i, p_j) = 1$, theo lý thuyết hàm nhân tính, ta có thể tính giá trị hàm tại $i \times p_j$ từ các giá trị tại $i$ và $p_j$.

Code sàng hàm $\mu$

isPrime[1] = mu[1] = 1;
for(int i = 2; i <= MAX; ++i){
    if(!isPrime[i]){
        primeList[++cnt] = i;
        mu[i] = -1;
    }
    for(int j = 1; j <= cnt && i * primeList[j] <= MAX; ++j){
        isPrime[i * primeList[j]] = 1;
        if(i % primeList[j] == 0){
            mu[i * primeList[j]] = 0;
            break;
        }
        mu[i * primeList[j]] = -mu[i];
    }
}

Code sàng hàm $\varphi$

isPrime[1] = phi[1] = 1;
for(int i = 2; i <= MAX; ++i){
    if(!isPrime[i]){
        primeList[++cnt] = i;
        phi[i] = i - 1;
    }
    for(int j = 1; j <= cnt && i * primeList[j] <= MAX; ++j){
        isPrime[i * primeList[j]] = 1;
        if(i % primeList[j] == 0){
            phi[i * primeList[j]] = phi[i] * primeList[j];
            break;
        }
        phi[i * primeList[j]] = phi[i] * phi[primeList[j]];
    }
}

Phép Nghịch Đảo Möbius

Định nghĩa các hàm đặc biệt:

• $I(n) = 1$ với mọi $n$
• $\varepsilon(n) = [n = 1]$ (hàm đơn vị)

Tính chất cơ bản

Tính chất 1: $\mu * I = \varepsilon$

Chứng minh: $\sum_{d \mid n} \mu(d) = [n = 1]$. Thật vậy, các số có từ hai thừa số nguyên tố trở lên không đóng góp vào tổng. Với các số chỉ chứa một thừa số nguyên tố, ta có tổng $\sum_{k=0}^{n} \binom{n}{k}(-1)^k = 0$ theo nhị thức Newton khi $x=1, y=-1$.

Tính chất 2: $\varphi * I = id$

Chứng minh: $\sum_{d \mid n} \varphi(d) = n$. Từ $\sum_{d \mid n}\sum_{i=1}^{n}[\gcd(i,n)=d] = n$, đặt $i = d \cdot t$, ta có $\sum_{d \mid n}\sum_{t=1}^{\lfloor n/d \rfloor}[\gcd(t, n/d)=1] = n$, tức là $\sum_{d \mid n}\varphi(d) = n$.

Tính chất 3: Từ hai tính chất trên, suy ra $id * \mu = \varphi$.

Công thức nghịch đảo

Nếu $f = g * I$, thì $g = f * \mu$. Đây chính là công thức nghịch đảo Möbius.

Thông thường, ta xây dựng cặp hàm $f, g$ thỏa mãn $f = g * I$, trong đó $f$ dễ tính toán, rồi sử dụng $g = f * \mu$ để tìm kết quả mong muốn.

Ứng Dụng

Bài toán 1: Tính tổng ước chung lớn nhất

Tính $\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$ với $n \le m$.

Bước 1: Đặt $d = \gcd(i,j)$, ta có:

$$\sum_{d=1}^{n} d \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]$$

Bước 2: Chia $d$ ra ngoài:

$$\sum_{d=1}^{n} d \sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor m/d \rfloor}[\gcd(i,j)=1]$$

Bước 3: Sử dụng tính chất $\mu$:

$$[\gcd(i,j)=1] = \sum_{k \mid \gcd(i,j)} \mu(k)$$

$$\sum_{d=1}^{n} d \sum_{k=1}^{\lfloor n/d \rfloor} \mu(k) \left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor$$

Bước 4: Đặt $T = kd$:

$$\sum_{T=1}^{n} \left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \sum_{d \mid T} d\mu\left(\frac{T}{d}\right)$$

Xét $f(T) = \sum_{d \mid T} \mu(d) \frac{T}{d}$. Đây là hàm nhân tính, và ta có thể chứng minh $f(T) = \varphi(T)$. Do đó:

$$\sum_{T=1}^{n} \left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \varphi(T)$$

Để tính nhanh, ta sử dụng kỹ thuật "chia khối" (division trick): các giá trị $\lfloor n/i \rfloor$ và $\lfloor m/i \rfloor$ có nhiều giá trị lặp lại, ta có thể tính cùng lúc.

Độ phức tạp: $O(\sqrt{n})$

Bài toán 2: Tích các số Fibonacci theo ước chung

Tính $\prod_{i=1}^{n}\prod_{j=1}^{m} F_{\gcd(i,j)}$ với $F$ là dãy Fibonacci, $n \le m$.

Tương tự bài trên:

$$\prod_{d=1}^{n} F_d^{\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]}$$

Sau các biến đổi, ta được:

$$\prod_{T=1}^{n} \left(\prod_{d \mid T} F_d^{\mu(T/d)}\right)^{\lfloor n/T \rfloor \lfloor m/T \rfloor}$$

Phần mũ có thể tính bằng chia khối, phần trong ngoặc cần tính trực tiếp.

Bài toán 3: Tổng tích với ước chung

Tính $\sum_{i=1}^{n}\sum_{j=1}^{n} ij\gcd(i,j)$

Đặt $d = \gcd(i,j)$, sau các biến đổi tương tự:

$$\sum_{T=1}^{n} T^2 \left(\sum_{i=1}^{\lfloor n/T \rfloor} i\right)^2 \varphi(T)$$

Đặt $S(k) = \sum_{i=1}^{k} i = \frac{k(k+1)}{2}$, ta có:

$$\sum_{T=1}^{n} T^2 S\left(\left\lfloor\frac{n}{T}\right\rfloor\right)^2 \varphi(T)$$

Bài toán trở thành tính $f(k) = k^2\varphi(k)$ có thể sàng tuyến tính, nhưng nếu $n \le 10^{10}$, ta cần đến sàng Du Jiao.

Sàng Du Jiao (杜教筛)

Giả sử cần tính $S(n) = \sum_{i=1}^{n} f(i)$ với $f$ là hàm nhân tính. Chọn một hàm nhân tính $g$ khác, ta có:

$$(f * g)(n) = \sum_{d \mid n} g(d) f\left(\frac{n}{d}\right) = \sum_{d=1}^{n} g(d) S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$

Tách $d = 1$:

$$g(1)S(n) = (f * g)(n) - \sum_{i=2}^{n} g(i) S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

$$S(n) = \frac{(f * g)(n) - \sum_{i=2}^{n} g(i) S(\lfloor n/i \rfloor)}{g(1)}$$

Nếu ta tính được $(f * g)(n)$ và prefix sum của $g$ nhanh, đệ quy tính $S$ với các giá trị nhỏ hơn và áp dụng chia khối.

Độ phức tạp: $O(n^{3/4})$, nếu precompute trước $n^{2/3}$ giá trị thì còn $O(n^{2/3})$.

Bộ nhớ

Sử dụng hash table (unordered_map) để lưu kết quả đệ quy. Một mẹo khác: với $x \le \sqrt{n}$, nó sẽ được precompute; với $x > \sqrt{n}$, các giá trị đệ quy $\frac{n}{x} \le \sqrt{n}$, nên ta chỉ cần mảng size $\sqrt{n}$.

Ví dụ: Tính tổng $\mu$

Do $\mu * I = \varepsilon$, chọn $g = I$, ta có $(f * g)(n) = 1$, prefix của $g$ là $n$. Code mẫu:

int solveMu(int x){
    if(x <= PRECALC) return prefixMu[x];
    if(memo[n / x]) return memo[n / x];
    
    int result = 1;
    for(int left = 2, right = 0; left <= x && right <= x; left = right + 1){
        right = x / (x / left);
        result -= (right - left + 1) * solveMu(x / left);
    }
    return memo[n / x] = result;
}

Tính $\sum i^2\varphi(i)$

Đặt $f(n) = n^2\varphi(n)$. Chọn $g(n) = n^2$, ta có:

$$(f * g)(n) = \sum_{d \mid n} d^2\varphi(d) \cdot \left(\frac{n}{d}\right)^2 = \sum_{d \mid n} n^2\varphi(d) = n^2 \sum_{d \mid n}\varphi(d) = n^3$$

Prefix của $g$: $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

Sử dụng công thức nghịch đảo, ta có thể tính $S(n) = \sum_{i=1}^{n} i^2\varphi(i)$ trong $O(n^{2/3})$.