Bài 2.1: Hàm số học cơ bản: hàm phi Euler, hàm Mobius, hàm sigma

Chào mừng các bạn đến với bài viết thứ hai trong chuỗi bài về Cấu trúc dữ liệu và Giải thuật (CTDL và GT). Sau khi làm quen với các khái niệm cơ bản, chúng ta sẽ đi sâu vào một lĩnh vực hấp dẫn của Toán học ứng dụng trong lập trình, đó là Lý thuyết số (Number Theory). Lý thuyết số cung cấp nền tảng cho rất nhiều giải thuật quan trọng, từ mã hóa, băm (hashing) cho đến các bài toán tối ưu và đếm trong các cuộc thi lập trình.

Trong bài này, chúng ta sẽ tìm hiểu về ba "ngôi sao" cơ bản nhất của các hàm số học (arithmetic functions) – những hàm số mà miền xác định là tập hợp các số nguyên dương: hàm phi Euler, hàm Mobius, và các biến thể của hàm sigma. Chúng không chỉ có định nghĩa đẹp đẽ mà còn sở hữu những tính chất mạnh mẽ, cho phép chúng ta giải quyết nhiều bài toán phức tạp một cách hiệu quả.

Hãy cùng bắt đầu hành trình khám phá những hàm số kỳ diệu này nhé!

1. Hàm Phi Euler ($\phi(n)$)

Hàm phi Euler, ký hiệu là $\phi(n)$ (hoặc đôi khi là $\varphi(n)$), là một trong những hàm số học quan trọng nhất.

Định nghĩa:

$\phi(n)$ được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng $n$ và nguyên tố cùng nhau với $n$. Hai số $a$ và $b$ được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất (GCD) của chúng là 1, tức là $\text{gcd}(a, b) = 1$.

Ví dụ:

$\phi(1) = 1$ (số 1 là nguyên tố cùng nhau với chính nó)
$\phi(2) = 1$ (chỉ có số 1 nguyên tố cùng nhau với 2, trong các số <= 2)
$\phi(3) = 2$ (số 1, 2 nguyên tố cùng nhau với 3, trong các số <= 3)
$\phi(4) = 2$ (số 1, 3 nguyên tố cùng nhau với 4, trong các số <= 4)
$\phi(6) = 2$ (số 1, 5 nguyên tố cùng nhau với 6, trong các số <= 6)

Tính chất quan trọng:

Hàm nhân tính (Multiplicative function): Nếu $m$ và $n$ là hai số nguyên tố cùng nhau ($\text{gcd}(m, n) = 1$), thì $\phi(mn) = \phi(m)\phi(n)$. Đây là một tính chất cực kỳ mạnh mẽ, cho phép chúng ta tính $\phi(n)$ dựa trên phân tích thừa số nguyên tố của $n$.
Công thức tính từ phân tích thừa số nguyên tố: Nếu phân tích thừa số nguyên tố của $n$ là $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, thì công thức tính $\phi(n)$ là: $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$ Tương đương với: $\phi(n) = n \frac{p_1-1}{p_1} \frac{p_2-1}{p_2} \cdots \frac{p_k-1}{p_k}$ Và còn có thể viết: $\phi(n) = p_1^{a_1-1}(p_1-1) p_2^{a_2-1}(p_2-1) \cdots p_k^{a_k-1}(p_k-1)$.

Cách tính $\phi(n)$:

Tính cho một số $n$ cụ thể: Sử dụng công thức từ phân tích thừa số nguyên tố. Đầu tiên, tìm tất cả các ước nguyên tố phân biệt của $n$. Sau đó áp dụng công thức.
Tính cho tất cả số $n$ từ 1 đến $N$ (Sàng Euler Phi): Đây là cách hiệu quả nhất khi cần tính $\phi$ cho một phạm vi lớn. Chúng ta có thể sử dụng một biến thể của sàng Eratosthenes.

Giải thuật Sàng Euler Phi:

Chúng ta tạo một mảng phi có kích thước $N+1$. Ban đầu, gán phi[i] = i cho tất cả $i$ từ 1 đến $N$. Sau đó, duyệt từ 2 đến $N$: nếu phi[i] == i (điều này chỉ xảy ra khi $i$ là số nguyên tố, vì các số hợp số đã bị cập nhật phi bởi các ước nguyên tố nhỏ hơn của chúng), thì $i$ là một ước nguyên tố. Với mỗi ước nguyên tố $i$, duyệt qua tất cả các bội của $i$ (là $i, 2i, 3i, \dots$) lên đến $N$ và cập nhật giá trị phi của chúng theo công thức. Cụ thể, với mỗi bội $j$ của $i$, phi[j] sẽ bị giảm đi phi[j] / i.

Công thức $\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})$ có thể được hiểu theo cách sàng như sau: Ban đầu, $\phi(n) = n$. Khi ta gặp một ước nguyên tố $p$ của $n$, ta "nhân" thêm $(1 - 1/p)$ vào công thức. Trong giải thuật sàng, khi ta duyệt qua số nguyên tố $p$ và các bội $kp$, ta biết $p$ là một ước nguyên tố của $kp$. Ta cần cập nhật $\phi(kp)$. Giá trị $\phi(kp)$ hiện tại đang là $kp$ (hoặc đã được cập nhật bởi các ước nguyên tố nhỏ hơn $p$). Việc trừ đi phi[kp] / p tương đương với việc nhân $\phi(kp)$ với $(1 - 1/p)$.

Ví dụ: Tính $\phi(6)$ bằng sàng.

Khởi tạo: $\phi = [?, 1, 2, 3, 4, 5, 6]$
$i=2$ (là nguyên tố vì $\phi[2]=2$): Duyệt bội của 2:
- $j=2$: $\phi[2] = \phi[2] - \phi[2]/2 = 2 - 2/2 = 1$.
- $j=4$: $\phi[4] = \phi[4] - \phi[4]/2 = 4 - 4/2 = 2$.
- $j=6$: $\phi[6] = \phi[6] - \phi[6]/2 = 6 - 6/2 = 3$.
Hiện tại: $\phi = [?, 1, 1, 3, 2, 5, 3]$.
$i=3$ (là nguyên tố vì $\phi[3]=3$): Duyệt bội của 3:
- $j=3$: $\phi[3] = \phi[3] - \phi[3]/3 = 3 - 3/3 = 2$.
- $j=6$: $\phi[6] = \phi[6] - \phi[6]/3 = 3 - 3/3 = 2$.
Kết quả cuối cùng cho các số <= 6: $\phi = [?, 1, 1, 2, 2, 4, 2]$. (Lưu ý $\phi(5)=4$, tôi gõ nhầm ở trên).

C++ Code: Sàng Euler Phi

#include <iostream>
#include <vector>
#include <numeric> // For std::gcd (C++17) or implement gcd manually

// Hàm tính phi(n) cho một số n bằng phân tích thừa số nguyên tố
long long phi_single(int n) {
    long long result = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1) // If n still has a prime factor > sqrt(original n)
        result -= result / n;
    return result;
}

// Sàng Euler Phi để tính phi(i) cho tất cả i từ 1 đến N
std::vector<int> sieve_phi(int N) {
    std::vector<int> phi(N + 1);
    for (int i = 0; i <= N; ++i) {
        phi[i] = i;
    }

    for (int i = 2; i <= N; ++i) {
        // If phi[i] is still i, it means i is prime
        if (phi[i] == i) {
            // For all multiples of i (including i itself)
            for (int j = i; j <= N; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
    return phi;
}

int main() {
    int N = 20;

    // Tính phi cho một số cụ thể
    int num_to_calc = 12;
    std::cout << "phi(" << num_to_calc << ") = " << phi_single(num_to_calc) << std::endl; // Output: phi(12) = 4 (1, 5, 7, 11)

    std::cout << "\nCalculating phi(i) for i from 1 to " << N << " using sieve:" << std::endl;
    std::vector<int> phi_values = sieve_phi(N);
    for (int i = 1; i <= N; ++i) {
        std::cout << "phi(" << i << ") = " << phi_values[i] << std::endl;
    }

    return 0;
}

Giải thích Code:

Hàm phi_single(int n): Tính $\phi(n)$ cho một số $n$ cụ thể. Nó lặp qua các số $i$ từ 2 đến $\sqrt{n}$. Nếu $i$ là ước của $n$, nó loại bỏ tất cả các thừa số $i$ khỏi $n$ và cập nhật result bằng cách trừ đi result / i. Nếu sau vòng lặp, $n > 1$, điều đó có nghĩa là phần còn lại của $n$ là một số nguyên tố lớn hơn $\sqrt{\text{original } n}$, và ta cập nhật result tương ứng. Độ phức tạp là $O(\sqrt{n})$.
Hàm sieve_phi(int N): Implement giải thuật sàng Euler Phi.
- Khởi tạo: Tạo vector phi kích thước N+1, gán phi[i] = i.
- Vòng lặp ngoài: Duyệt $i$ từ 2 đến $N$.
- Kiểm tra nguyên tố: if (phi[i] == i) kiểm tra xem $i$ có phải là số nguyên tố chưa bị sàng bởi các số nhỏ hơn hay không.
- Vòng lặp trong (sàng): Nếu $i$ là nguyên tố, duyệt qua tất cả các bội $j = i, 2i, 3i, \dots$ lên đến $N$. Với mỗi bội $j$, cập nhật phi[j] -= phi[j] / i.
- Độ phức tạp của sàng này là $O(N \log \log N)$, rất hiệu quả cho phạm vi lớn.

2. Hàm Mobius ($\mu(n)$)

Hàm Mobius, ký hiệu là $\mu(n)$, là một hàm số học quan trọng khác, có liên hệ sâu sắc với cấu trúc nguyên tố của các số. Nó đóng vai trò trung tâm trong công thức nghịch đảo Mobius (Mobius inversion formula).

Định nghĩa:

Hàm Mobius $\mu(n)$ được định nghĩa cho các số nguyên dương $n$ như sau:

$\mu(1) = 1$
$\mu(n) = 0$ nếu $n$ có bất kỳ ước nguyên tố nào xuất hiện với lũy thừa lớn hơn 1 (tức là $n$ không phải là số vuông tự do - square-free).
$\mu(n) = (-1)^k$ nếu $n$ là số vuông tự do và có đúng $k$ thừa số nguyên tố phân biệt.

Ví dụ:

$\mu(1) = 1$
$\mu(2) = -1$ (2 = 2^1, vuông tự do, 1 thừa số nguyên tố)
$\mu(3) = -1$ (3 = 3^1, vuông tự do, 1 thừa số nguyên tố)
$\mu(4) = 0$ (4 = 2^2, không vuông tự do)
$\mu(5) = -1$ (5 = 5^1, vuông tự do, 1 thừa số nguyên tố)
$\mu(6) = 1$ (6 = 2^1 * 3^1, vuông tự do, 2 thừa số nguyên tố)
$\mu(10) = 1$ (10 = 2^1 * 5^1, vuông tự do, 2 thừa số nguyên tố)
$\mu(12) = 0$ (12 = 2^2 * 3^1, không vuông tự do)

Tính chất quan trọng:

Hàm nhân tính: Nếu $m$ và $n$ là hai số nguyên tố cùng nhau ($\text{gcd}(m, n) = 1$), thì $\mu(mn) = \mu(m)\mu(n)$.
Tổng các giá trị Mobius trên các ước: Một tính chất rất đẹp và quan trọng: $\sum_{d|n} \mu(d) = [n=1]$ trong đó $[n=1]$ là ký hiệu Iverson, bằng 1 nếu $n=1$ và bằng 0 nếu $n > 1$. Tổng này được tính trên tất cả các ước dương $d$ của $n$.

Cách tính $\mu(n)$:

Tính cho một số $n$ cụ thể: Phân tích thừa số nguyên tố của $n$. Nếu bất kỳ thừa số nào có lũy thừa > 1, $\mu(n)=0$. Ngược lại, đếm số lượng thừa số nguyên tố phân biệt $k$, rồi $\mu(n) = (-1)^k$.
Tính cho tất cả số $n$ từ 1 đến $N$ (Sàng Mobius): Tương tự như $\phi(n)$, chúng ta có thể sử dụng một giải thuật sàng hiệu quả.

Giải thuật Sàng Mobius:

Chúng ta có thể sử dụng một sàng tương tự sàng Eratosthenes, hoặc tốt hơn là sàng tuyến tính (linear sieve) để tính $\mu(n)$ cùng lúc với việc tìm các số nguyên tố hoặc ước nguyên tố nhỏ nhất.

Sử dụng Sàng Tuyến Tính để tính $\mu(n)$:

Tạo mảng mu kích thước $N+1$, mảng spf (smallest prime factor) kích thước $N+1$, và một vector primes để lưu các số nguyên tố.
Khởi tạo mu[1] = 1.
Duyệt $i$ từ 2 đến $N$.
- Nếu spf[i] == 0 (nghĩa là $i$ chưa bị sàng bởi số nào nhỏ hơn, vậy $i$ là số nguyên tố), gán spf[i] = i, mu[i] = -1, và thêm $i$ vào danh sách primes.
- Với mỗi số nguyên tố $p$ trong danh sách primes sao cho $p \le spf[i]$ và $i \cdot p \le N$:
  - Gán spf[i * p] = p.
  - Nếu $p == spf[i]$ (nghĩa là $i$ đã chứa thừa số nguyên tố $p$ với lũy thừa $\ge 1$, vậy $i \cdot p$ sẽ chứa $p$ với lũy thừa $\ge 2$), gán mu[i * p] = 0.
  - Nếu $p < spf[i]$ (nghĩa là $p$ là ước nguyên tố nhỏ nhất của $i \cdot p$ và $p$ chưa xuất hiện trong phân tích của $i$), gán mu[i * p] = -mu[i] (vì $i$ và $p$ nguyên tố cùng nhau, $\mu(i \cdot p) = \mu(i) \mu(p) = \mu(i) \cdot (-1) = -\mu(i)$).
  - Ngừng vòng lặp khi $p > spf[i]$ vì các bội $i \cdot p'$ với $p' > spf[i]$ sẽ có $spf[i \cdot p'] = spf[i]$, và chúng sẽ được xử lý khi $i$ lớn hơn.

C++ Code: Sàng Mobius (Linear Sieve)

#include <iostream>
#include <vector>
#include <numeric>

// Sàng Mobius để tính mu(i) cho tất cả i từ 1 đến N
std::vector<int> sieve_mobius(int N) {
    std::vector<int> mu(N + 1);
    std::vector<int> spf(N + 1, 0); // smallest prime factor
    std::vector<int> primes;

    mu[1] = 1;

    for (int i = 2; i <= N; ++i) {
        if (spf[i] == 0) { // i is prime
            spf[i] = i;
            primes.push_back(i);
            mu[i] = -1;
        }

        for (int p : primes) {
            if (p > spf[i] || i * p > N) {
                break;
            }
            spf[i * p] = p;
            if (p == spf[i]) {
                mu[i * p] = 0; // i*p is divisible by p^2
            } else {
                mu[i * p] = -mu[i]; // i and p are coprime, mu(ip) = mu(i)mu(p) = mu(i)*(-1)
            }
        }
    }
    return mu;
}

int main() {
    int N = 20;
    std::cout << "Calculating mu(i) for i from 1 to " << N << " using sieve:" << std::endl;
    std::vector<int> mu_values = sieve_mobius(N);
    for (int i = 1; i <= N; ++i) {
        std::cout << "mu(" << i << ") = " << mu_values[i] << std::endl;
    }

    return 0;
}

Giải thích Code:

Hàm sieve_mobius(int N): Implement sàng Mobius tuyến tính.
- mu: Lưu giá trị $\mu(i)$.
- spf: Lưu ước nguyên tố nhỏ nhất của $i$. Được dùng để tối ưu vòng lặp trong sàng tuyến tính.
- primes: Lưu danh sách các số nguyên tố tìm được.
- Khởi tạo mu[1] = 1.
- Vòng lặp ngoài: Duyệt $i$ từ 2 đến $N$.
- Nếu $i$ là nguyên tố (spf[i] == 0), nó là ước nguyên tố nhỏ nhất của chính nó (spf[i] = i), $\mu(i) = -1$, và thêm vào danh sách primes.
- Vòng lặp trong: Duyệt qua các số nguyên tố $p$ đã tìm được.
  - Điều kiện p > spf[i] || i * p > N đảm bảo tính tuyến tính: mỗi hợp số $i \cdot p$ chỉ bị sàng một lần bởi ước nguyên tố nhỏ nhất của nó, đó chính là spf[i*p] = p. Nếu $p > spf[i]$, thì $spf[i \cdot p]$ sẽ là $spf[i]$, không phải $p$, nên ta dừng lại.
  - spf[i * p] = p: Đánh dấu $p$ là ước nguyên tố nhỏ nhất của $i \cdot p$.
  - if (p == spf[i]): Nếu $p$ đã là ước nguyên tố nhỏ nhất của $i$, thì $i \cdot p$ chứa $p$ với lũy thừa ít nhất là 2. Do đó, $i \cdot p$ không phải là số vuông tự do, và $\mu(i \cdot p) = 0$.
  - else: Nếu $p < spf[i]$, thì $p$ không chia hết cho bất kỳ ước nguyên tố nào của $i$. Điều này có nghĩa là $i$ và $p$ nguyên tố cùng nhau. Do tính nhân tính của $\mu$, $\mu(i \cdot p) = \mu(i) \mu(p) = \mu(i) \cdot (-1) = -\mu(i)$.
- Độ phức tạp của sàng Mobius tuyến tính là $O(N)$.

3. Hàm Sigma ($\sigma_k(n)$)

Hàm sigma, ký hiệu là $\sigma_k(n)$, là hàm tính tổng lũy thừa bậc $k$ của các ước của $n$.

Định nghĩa:

$\sigma_k(n)$ được định nghĩa là tổng của lũy thừa bậc $k$ của tất cả các ước dương của $n$. $\sigma_k(n) = \sum_{d|n} d^k$ trong đó tổng được tính trên tất cả các ước dương $d$ của $n$.

Hai trường hợp phổ biến nhất là:

$k=0$: $\sigma_0(n)$ là tổng lũy thừa bậc 0 của các ước, tức là $d^0=1$. Do đó, $\sigma_0(n)$ là số lượng các ước dương của $n$. Hàm này thường được ký hiệu là $d(n)$ hoặc $\tau(n)$.
$k=1$: $\sigma_1(n)$ là tổng lũy thừa bậc 1 của các ước, tức là $d^1=d$. Do đó, $\sigma_1(n)$ là tổng của tất cả các ước dương của $n$. Hàm này thường được ký hiệu là $\sigma(n)$.

Ví dụ:

$n=6$. Các ước dương là 1, 2, 3, 6.
- $\sigma_0(6) = 1^0 + 2^0 + 3^0 + 6^0 = 1 + 1 + 1 + 1 = 4$. (Có 4 ước: 1, 2, 3, 6)
- $\sigma_1(6) = 1^1 + 2^1 + 3^1 + 6^1 = 1 + 2 + 3 + 6 = 12$.

Tính chất quan trọng:

Hàm nhân tính: Đối với bất kỳ $k$ cố định nào, $\sigma_k(n)$ là một hàm nhân tính. Nếu $m$ và $n$ là hai số nguyên tố cùng nhau ($\text{gcd}(m, n) = 1$), thì $\sigma_k(mn) = \sigma_k(m)\sigma_k(n)$.
Công thức tính từ phân tích thừa số nguyên tố: Nếu phân tích thừa số nguyên tố của $n$ là $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$, thì công thức tính $\sigma_k(n)$ là: $\sigma_k(n) = \sigma_k(p_1^{a_1}) \sigma_k(p_2^{a_2}) \cdots \sigma_k(p_r^{a_r})$ Và $\sigma_k(p^a) = 1^k + p^k + p^{2k} + \cdots + p^{ak}$. Đây là một tổng cấp số nhân. Do đó, $\sigma_k(p^a) = \frac{p^{(a+1)k} - 1}{p^k - 1}$ (nếu $p^k \neq 1$). Nếu $k=0$, $\sigma_0(p^a) = 1 + 1 + \cdots + 1$ ($a+1$ lần) $= a+1$. Nếu $k \neq 0$, $\sigma_k(p^a) = 1 + p^k + \dots + p^{ak}$.
- $\sigma_0(n) = (a_1+1)(a_2+1)\cdots(a_r+1)$
- $\sigma_1(n) = \frac{p_1^{a_1+1} - 1}{p_1 - 1} \frac{p_2^{a_2+1} - 1}{p_2 - 1} \cdots \frac{p_r^{a_r+1} - 1}{p_r - 1}$

Cách tính $\sigma_k(n)$:

Tính cho một số $n$ cụ thể: Phân tích thừa số nguyên tố của $n$, sau đó áp dụng công thức.
Tính cho tất cả số $n$ từ 1 đến $N$ (Sàng Sigma): Chúng ta có thể sử dụng một giải thuật sàng đơn giản để tính $\sigma_0(n)$ và $\sigma_1(n)$.

Giải thuật Sàng Sigma (cho $\sigma_0$ và $\sigma_1$):

Đây là một sàng đơn giản hơn sàng tuyến tính.

Tạo hai mảng sigma0 và sigma1 có kích thước $N+1$.
Khởi tạo sigma0[i] = 0 và sigma1[i] = 0 cho tất cả $i$.
Duyệt $i$ từ 1 đến $N$. Số $i$ này đóng vai trò là một ước tiềm năng.
Với mỗi $i$, duyệt qua tất cả các bội $j = i, 2i, 3i, \dots$ lên đến $N$.
- Đối với mỗi bội $j$, $i$ là một ước của $j$. Do đó, ta tăng số lượng ước của $j$: sigma0[j]++.
- Và cộng giá trị của ước $i$ vào tổng các ước của $j$: sigma1[j] += i.

C++ Code: Sàng Sigma (cho $\sigma_0$ và $\sigma_1$)

#include <iostream>
#include <vector>
#include <cmath> // For std::pow or just loop for powers

// Hàm tính sigma_k(n) cho một số n cụ thể bằng phân tích thừa số nguyên tố
// Chỉ minh họa cho k=0 và k=1
long long sigma_single(int n, int k) {
    if (n == 1) return 1;
    long long result = 1;
    int temp_n = n;
    for (int i = 2; i * i <= temp_n; ++i) {
        if (temp_n % i == 0) {
            int count = 0;
            while (temp_n % i == 0) {
                temp_n /= i;
                count++;
            }
            // Calculate sigma_k(p^count)
            long long term = 0;
            if (k == 0) {
                term = count + 1;
            } else { // For k=1
                long long current_power_p = 1;
                for(int j=0; j<=count; ++j) {
                    term += current_power_p;
                    current_power_p *= i;
                }
            }
            result *= term;
        }
    }
    if (temp_n > 1) { // Remaining prime factor > sqrt(original n)
        int count = 1;
         long long term = 0;
         if (k == 0) {
             term = count + 1;
         } else { // For k=1
             long long current_power_p = 1;
             for(int j=0; j<=count; ++j) {
                 term += current_power_p;
                 current_power_p *= temp_n; // temp_n is the prime
             }
         }
         result *= term;
    }
    return result;
}


// Sàng Sigma để tính sigma0(i) và sigma1(i) cho tất cả i từ 1 đến N
std::pair<std::vector<int>, std::vector<long long>> sieve_sigma(int N) {
    std::vector<int> sigma0(N + 1, 0); // Number of divisors
    std::vector<long long> sigma1(N + 1, 0); // Sum of divisors

    for (int i = 1; i <= N; ++i) {
        for (int j = i; j <= N; j += i) {
            sigma0[j]++;
            sigma1[j] += i;
        }
    }
    return {sigma0, sigma1};
}

int main() {
    int N = 20;

    // Tính sigma cho một số cụ thể
    int num_to_calc = 12; // Divisors: 1, 2, 3, 4, 6, 12
    std::cout << "sigma0(" << num_to_calc << ") = " << sigma_single(num_to_calc, 0) << std::endl; // Output: sigma0(12) = 6
    std::cout << "sigma1(" << num_to_calc << ") = " << sigma_single(num_to_calc, 1) << std::endl; // Output: sigma1(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28

    std::cout << "\nCalculating sigma0(i) and sigma1(i) for i from 1 to " << N << " using sieve:" << std::endl;
    auto sigma_values = sieve_sigma(N);
    std::vector<int>& sigma0_values = sigma_values.first;
    std::vector<long long>& sigma1_values = sigma_values.second;

    for (int i = 1; i <= N; ++i) {
        std::cout << "sigma0(" << i << ") = " << sigma0_values[i]
                  << ", sigma1(" << i << ") = " << sigma1_values[i] << std::endl;
    }

    return 0;
}

Giải thích Code:

Hàm sigma_single(int n, int k): Tính $\sigma_k(n)$ cho một số $n$ cụ thể. Nó phân tích thừa số nguyên tố của $n$, đếm số mũ count cho mỗi thừa số nguyên tố $p$, sau đó tính $\sigma_k(p^{\text{count}})$ và nhân vào kết quả cuối cùng. Code này chỉ triển khai cho $k=0$ và $k=1$.
Hàm sieve_sigma(int N): Implement giải thuật sàng Sigma.
- sigma0 và sigma1: Lưu số lượng ước và tổng các ước tương ứng.
- Vòng lặp ngoài: Duyệt $i$ từ 1 đến $N$. $i$ là một ước.
- Vòng lặp trong: Duyệt qua tất cả các bội $j = i, 2i, 3i, \dots$ lên đến $N$.
- sigma0[j]++: Với mỗi bội $j$, số $i$ là một ước của $j$, nên số lượng ước của $j$ tăng lên 1.
- sigma1[j] += i: Với mỗi bội $j$, số $i$ là một ước của $j$, nên tổng các ước của $j$ tăng thêm $i$.
- Độ phức tạp của sàng này là $O(N \log N)$ vì vòng lặp trong chạy $N/i$ lần cho mỗi $i$, và tổng $\sum_{i=1}^N N/i = N \sum_{i=1}^N 1/i \approx N \log N$.

Liên hệ giữa các hàm số học

Ba hàm $\phi(n)$, $\mu(n)$, và $\sigma_k(n)$ đều là các hàm nhân tính. Tính chất này là cực kỳ quan trọng và cho phép tính toán chúng hiệu quả dựa trên phân tích thừa số nguyên tố hoặc bằng các giải thuật sàng.

Một mối liên hệ sâu sắc giữa hàm $\phi$ và hàm $\mu$ là qua công thức nghịch đảo Mobius. Nếu một hàm số học $f(n)$ được định nghĩa là tổng của hàm số học $g(d)$ trên tất cả các ước $d$ của $n$: $f(n) = \sum_{d|n} g(d)$ Thì ta có thể "nghịch đảo" để tìm $g(n)$ từ $f(n)$ bằng công thức: $g(n) = \sum_{d|n} \mu(d) f(n/d)$

Một ví dụ kinh điển là mối liên hệ giữa $n$ và $\phi(n)$: Ta có tính chất $\sum_{d|n} \phi(d) = n$. Ở đây, $f(n) = n$ và $g(n) = \phi(n)$. Áp dụng công thức nghịch đảo Mobius: $\phi(n) = \sum_{d|n} \mu(d) (n/d)$ Công thức này chính là một cách khác để biểu diễn công thức tính $\phi(n)$ từ phân tích thừa số nguyên tố mà chúng ta đã biết: $\phi(n) = n \sum_{d|n} \frac{\mu(d)}{d}$. Chỉ những ước $d$ là vuông tự do mới có $\mu(d) \neq 0$.

Tương tự, hàm $\sigma_1(n)$ (tổng các ước) cũng liên hệ với hàm đồng nhất $I(n) = n$. Ta có $\sigma_1(n) = \sum_{d|n} d = \sum_{d|n} I(d)$. Đây là trường hợp $f(n) = \sigma_1(n)$ và $g(n) = I(n) = n$. Công thức nghịch đảo Mobius trong trường hợp này là: $I(n) = \sum_{d|n} \mu(d) \sigma_1(n/d)$.

Bài tập ví dụ:

Luyện tập viết hàm

Cho số nguyên n không âm. Viết hàm xử lý các yêu cầu sau:

Kiểm tra n là số nguyên tố, nếu đúng in 1, sai in 0.
In tổng chữ số của n.
In tổng chữ số chẵn của n.
In tổng chữ số của n là số nguyên tố.
In số lật ngược của n. Ví dụ: 123 in 321.
In số lượng ước riêng biệt của n là số nguyên tố (làm tương tự như phân tích thừa số nguyên tố).
In ước nguyên tố lớn nhất của n (làm tương tự như phân tích thừa số nguyên tố).
Kiểm tra nếu n tồn tại ít nhất 1 số 6, nếu đúng in 1, sai in 0.
Kiểm tra nếu tổng chữ số của n chia hết cho 8, nếu đúng in 1, sai in 0.
Tính tổng giai thừa các chữ số của n và in ra. Ví dụ: n = 123, tổng = 1! + 2! + 3!.
Kiểm tra n có phải chỉ được tạo bởi 1 số hay không? Ví dụ: 222, 333, 99999. Đúng in ra 1, sai in ra 0.
Kiểm tra n có phải có chữ số tận cùng là lớn nhất hay không, tức là không có chữ số nào của n lớn hơn chữ số hàng đơn vị của nó. Nếu đúng in 1, sai in 0.
In tổng lũy thừa chữ số của n với cơ số là số chữ số. Ví dụ: 123 thì tính 1^3 + 2^3 + 3^3.

Input Format

Số duy nhất n (2 ≤ n ≤ 1000).

Constraints

Không có ràng buộc thêm.

Output Format

In ra 13 dòng tương ứng với các yêu cầu ở trên.

Sample Input 0

Sample Output 0

Chào bạn, đây là hướng dẫn giải bài tập này bằng C++ mà không cung cấp code hoàn chỉnh:

Bài tập yêu cầu xử lý một số nguyên không âm n và thực hiện 13 yêu cầu khác nhau, mỗi kết quả in ra một dòng. Bạn nên viết các hàm riêng biệt cho mỗi yêu cầu để luyện tập.

Input: Một số nguyên n (2 ≤ n ≤ 1000).

Output: 13 dòng kết quả.

Hướng dẫn chi tiết từng yêu cầu:

Kiểm tra số nguyên tố:
- Viết hàm bool isPrime(int k).
- Số nguyên tố là số lớn hơn 1 chỉ chia hết cho 1 và chính nó.
- Với k <= 1, không phải số nguyên tố.
- Với k > 1, kiểm tra xem k có chia hết cho bất kỳ số nào từ 2 đến sqrt(k) hay không. Nếu có, không phải số nguyên tố.
- Nếu không chia hết cho số nào trong khoảng đó, là số nguyên tố.
- Gọi hàm với n và in kết quả (1 hoặc 0).
Tổng chữ số:
- Viết hàm int sumDigits(int k).
- Khởi tạo tổng bằng 0.
- Dùng vòng lặp while (k > 0).
- Trong mỗi lần lặp: lấy chữ số cuối cùng bằng k % 10, cộng vào tổng. Cập nhật k = k / 10.
- Hàm trả về tổng.
- Gọi hàm với n và in kết quả.
Tổng chữ số chẵn:
- Viết hàm int sumEvenDigits(int k).
- Tương tự như tổng chữ số, nhưng chỉ cộng chữ số vào tổng nếu nó là số chẵn (chữ số % 2 == 0).
- Gọi hàm với n và in kết quả.
Tổng chữ số là số nguyên tố:
- Viết hàm int sumPrimeDigits(int k).
- Tương tự như tổng chữ số, nhưng chỉ cộng chữ số vào tổng nếu nó là số nguyên tố. Các chữ số từ 0-9 là số nguyên tố bao gồm: 2, 3, 5, 7.
- Gọi hàm với n và in kết quả.
Số lật ngược:
- Viết hàm int reverseNumber(int k).
- Khởi tạo số lật ngược reversed_n = 0.
- Dùng vòng lặp while (k > 0).
- Trong mỗi lần lặp: lấy chữ số cuối digit = k % 10. Cập nhật reversed_n = reversed_n * 10 + digit. Cập nhật k = k / 10.
- Hàm trả về reversed_n.
- Gọi hàm với n và in kết quả.
Số lượng ước nguyên tố riêng biệt:
- Viết hàm int countDistinctPrimeFactors(int k).
- Sử dụng một std::set<int> để lưu các ước nguyên tố duy nhất.
- Dùng vòng lặp với biến d bắt đầu từ 2.
- Trong khi k > 1 và d * d <= k:
  - Nếu k chia hết cho d: d là ước nguyên tố. Thêm d vào set. Chia k cho d liên tục cho đến khi không chia hết nữa.
  - Nếu k không chia hết cho d: tăng d lên 1.
- Nếu sau vòng lặp mà k > 1, điều đó có nghĩa là k còn lại là một số nguyên tố lớn hơn sqrt(n) ban đầu. Thêm k vào set.
- Kích thước của set chính là số lượng ước nguyên tố riêng biệt.
- Gọi hàm với n và in kết quả.
Ước nguyên tố lớn nhất:
- Viết hàm int largestPrimeFactor(int k).
- Khởi tạo largest_factor = 0.
- Tương tự như phân tích thừa số nguyên tố ở trên. Mỗi khi tìm thấy một ước nguyên tố d hoặc phần k còn lại sau cùng, cập nhật largest_factor = max(largest_factor, d) hoặc largest_factor = max(largest_factor, k).
- Gọi hàm với n và in kết quả.
Kiểm tra tồn tại số 6:
- Viết hàm bool containsDigitSix(int k).
- Dùng vòng lặp while (k > 0). Lấy chữ số cuối digit = k % 10.
- Nếu digit == 6, hàm trả về true ngay lập tức.
- Nếu vòng lặp kết thúc mà không tìm thấy số 6, hàm trả về false.
- Gọi hàm với n và in kết quả (1 hoặc 0).
Tổng chữ số chia hết cho 8:
- Viết hàm bool isSumDigitsDivisibleByEight(int k).
- Tính tổng chữ số của k (tái sử dụng logic từ yêu cầu 2).
- Kiểm tra xem tổng này có chia hết cho 8 hay không (tổng % 8 == 0).
- Hàm trả về kết quả kiểm tra.
- Gọi hàm với n và in kết quả (1 hoặc 0).
Tổng giai thừa các chữ số:
- Viết hàm long long factorial(int digit) để tính giai thừa của một chữ số (0! = 1, 1! = 1, ..., 9! = 362880).
- Viết hàm long long sumFactorialDigits(int k).
- Khởi tạo tổng bằng 0.
- Dùng vòng lặp while (k > 0). Lấy chữ số cuối digit = k % 10.
- Cộng factorial(digit) vào tổng. Cập nhật k = k / 10.
- Hàm trả về tổng. Sử dụng long long cho tổng để tránh tràn số vì 9! khá lớn.
- Gọi hàm với n và in kết quả.
Kiểm tra chỉ tạo bởi 1 số:
- Viết hàm bool areAllDigitsSame(int k).
- Nếu k < 10, trả về true (số có 1 chữ số).
- Lấy chữ số cuối cùng làm mẫu last_digit = k % 10.
- Cập nhật k = k / 10.
- Dùng vòng lặp while (k > 0). Lấy chữ số cuối mới digit = k % 10.
- Nếu digit != last_digit, trả về false.
- Cập nhật k = k / 10.
- Nếu vòng lặp kết thúc, tất cả các chữ số đều giống chữ số cuối cùng ban đầu, trả về true.
- Gọi hàm với n và in kết quả (1 hoặc 0).
Chữ số tận cùng lớn nhất:
- Viết hàm bool isLastDigitMax(int k).
- Nếu k < 10, trả về true (chỉ có 1 chữ số).
- Lấy chữ số cuối cùng last_digit = k % 10.
- Cập nhật k = k / 10.
- Dùng vòng lặp while (k > 0). Lấy chữ số cuối mới digit = k % 10.
- Nếu digit > last_digit, trả về false.
- Cập nhật k = k / 10.
- Nếu vòng lặp kết thúc, không có chữ số nào lớn hơn chữ số tận cùng, trả về true.
- Gọi hàm với n và in kết quả (1 hoặc 0).
Tổng lũy thừa chữ số với cơ số là số chữ số:
- Viết hàm int countDigits(int k) để đếm số chữ số (tương tự logic lặp của tổng chữ số, chỉ tăng bộ đếm).
- Viết hàm long long power(int base, int exp) để tính lũy thừa base^exp (dùng vòng lặp nhân hoặc pow từ cmath và làm tròn/ép kiểu).
- Viết hàm long long sumPowersDigits(int k).
- Đếm số chữ số của k ban đầu, lưu vào biến num_digits.
- Khởi tạo tổng sum = 0.
- Sử dụng một bản sao của k để trích xuất chữ số (vì bản gốc cần để đếm số chữ số).
- Dùng vòng lặp while (temp_k > 0). Lấy chữ số cuối digit = temp_k % 10.
- Cộng power(digit, num_digits) vào tổng. Cập nhật temp_k = temp_k / 10.
- Hàm trả về tổng. Sử dụng long long cho tổng.
- Gọi hàm với n và in kết quả.