Thi đấu

Phi Hàm Euler và Ứng Dụng Trong Đồng Dư Số Học

Phi hàm Euler phi(n) đếm số lượng số nguyên tố cùng nhau với n, đóng vai trò nền tảng trong số học thi đấu, định lý Euler và các bài toán tính lũy thừa lớn theo modulo.

Phi Hàm Euler và Ứng Dụng Trong Đồng Dư Số Học

Trong lý thuyết số học và mật mã học hiện đại, Phi hàm Euler (kí hiệu là \(\phi(n)\) hay Euler's Totient Function) giữ một vị trí trung tâm vô cùng quan trọng. Hàm số này được nhà toán học vĩ đại Leonhard Euler giới thiệu vào thế kỷ 18, định nghĩa số lượng các số nguyên dương nằm trong đoạn từ \(1\) đến \(n\) nguyên tố cùng nhau với \(n\) (nghĩa là có ước chung lớn nhất \(\gcd(x, n) = 1\)).

Đối với các lập trình viên thi đấu, phi hàm Euler không chỉ là một bài toán đếm đơn thuần mà còn là chìa khóa để giải quyết bài toán tính lũy thừa siêu lớn \(A^B \pmod M\) khi số mũ \(B\) vượt quá giới hạn \(10^{18}\) hoặc khi modulo \(M\) là một hợp số bất kỳ. Định lý Euler đóng vai trò như chiếc chìa khóa vàng giúp thu gọn số mũ về một phạm vi tính toán an toàn.

Bài viết này sẽ trình bày trọn vẹn lý thuyết toán học đằng sau phi hàm Euler, chứng minh công thức tích Euler, so sánh thuật toán tính đơn lẻ trong \(O(\sqrt{N})\) với thuật toán sàng phi hàm trong \(O(N \log \log N)\), đồng thời minh họa cách ứng dụng định lý Euler để giải quyết các bài toán lũy thừa tầng hóc búa.

1. Định nghĩa và Công thức tích Euler

Theo định nghĩa toán học: \[\phi(n) = \sum_{i=1}^n [\gcd(i, n) == 1]\]

Bảng giá trị của \(\phi(n)\) cho các số nguyên đầu tiên:

  • \(\phi(1) = 1\) (số 1 nguyên tố cùng nhau với chính nó).
  • \(\phi(2) = 1\) (chỉ có số 1).
  • \(\phi(3) = 2\) (gồm \(\{1, 2\}\)).
  • \(\phi(4) = 2\) (gồm \(\{1, 3\}\)).
  • \(\phi(5) = 4\) (với mọi số nguyên tố \(p\), \(\phi(p) = p - 1\)).
  • \(\phi(6) = 2\) (gồm \(\{1, 5\}\)).
Phi Hàm Euler (Totient Function) & Sàng Phi Hàm O(N log log N) Đếm số các số nguyên tố cùng nhau với N trong đoạn [1, N] -> Ví dụ phi(36) = 12 Công thức Tích Euler (Euler's Product) Nếu N = p1^a1 * p2^a2 * ... * pk^ak: phi(N) = N * ∏ (1 - 1/p) Thuật toán tính đơn lẻ: O(sqrt(N)) Ví dụ N = 36 = 2^2 * 3^2: phi(36) = 36 * (1 - 1/2) * (1 - 1/3) phi(36) = 36 * 1/2 * 2/3 = 12 Sàng Phi hàm Euler từ 1 đến 12 Khởi tạo: phi[i] = i với mọi i trong [1, 12] • Duyệt p = 2: phi[i] -= phi[i] / 2 với i % 2 == 0 • Duyệt p = 3: phi[i] -= phi[i] / 3 với i % 3 == 0 Bảng kết quả sau sàng: i : 1 2 3 4 5 6 7 8 9 10 11 12 phi : 1 1 2 2 4 2 6 4 6 4 10 4
Phi Hàm Euler & Sàng O(N log log N) Đếm số nguyên tố cùng nhau với N Công thức tích Euler: phi(N) = N * ∏ (1 - 1/p) • p là các ước nguyên tố phân biệt của N Sàng phi(N) tương tự sàng Eratosthenes Chạy tay N = 36: Ước nguyên tố: 2 và 3 phi(36) = 36 * (1/2) * (2/3) = 12 12 số nguyên tố cùng nhau: {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}
Sơ đồ tính phi hàm Euler phi(36) = 12 bằng công thức tích Euler và cách sàng phi hàm.

Tính chất nhân tính (Multiplicative Function)

Phi hàm Euler là một hàm số nhân tính: nếu hai số \(a\) và \(b\) nguyên tố cùng nhau (\(\gcd(a, b) = 1\)) thì: \[\phi(a \cdot b) = \phi(a) \cdot \phi(b)\]

Công thức với lũy thừa số nguyên tố

Nếu \(p\) là một số nguyên tố và \(k \ge 1\): Trong đoạn \([1, p^k]\), các số không nguyên tố cùng nhau với \(p^k\) bắt buộc phải là bội số của \(p\). Các bội số đó là: \(1p, 2p, 3p, \dots, p^{k-1}p\). Có đúng \(p^{k-1}\) bội số như vậy. Do đó: \[\phi(p^k) = p^k - p^{k-1} = p^k \left( 1 - \frac{1}{p} \right)\]

Công thức tích tổng quát của Euler (Euler's Product Formula)

Xét số nguyên dương \(n\) có phân tích thừa số nguyên tố duy nhất: \[n = p_1^{a_1} \cdot p_2^{a_2} \dots p_k^{a_k}\] Áp dụng tính chất nhân tính: \[\phi(n) = \prod_{i=1}^k \phi(p_i^{a_i}) = \prod_{i=1}^k p_i^{a_i} \left( 1 - \frac{1}{p_i} \right)\] Vì \(\prod_{i=1}^k p_i^{a_i} = n\) nên: \[\phi(n) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right)\]

Ví dụ: Tính \(\phi(36)\): \(36 = 2^2 \times 3^2\). Các thừa số nguyên tố phân biệt là 2 và 3. \[\phi(36) = 36 \times \left( 1 - \frac{1}{2} \right) \times \left( 1 - \frac{1}{3} \right)\] tức là \(\phi(36) = 36 \times \frac{1}{2} \times \frac{2}{3} = 12\). Tập 12 số nguyên tố cùng nhau với 36 nhỏ hơn 36 là: \(\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}\).

2. Các thuật toán tính Phi hàm Euler trong lập trình

Tùy vào bối cảnh bài toán, chúng ta lựa chọn thuật toán phù hợp:

Thuật toán 1: Tính phi(N) cho một số đơn lẻ trong O(sqrt(N))

Dựa trực tiếp vào công thức tích Euler: ta duyệt tìm các ước số nguyên tố \(p\) từ \(2\) đến \(\sqrt{N}\). Mỗi khi tìm thấy một ước \(p\), ta trừ bớt \(res / p\) và chia triệt tiêu \(p\) khỏi \(N\):

long long phi(long long n) {
    long long res = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

Thuật toán 2: Sàng Phi hàm Euler từ 1 đến M trong O(M log log M)

Khi cần trả lời nhiều truy vấn hoặc cần tính tổng phi hàm trên một đoạn lớn \(M = 10^6\), ta sử dụng kỹ thuật sàng tương tự sàng nguyên tố Eratosthenes:

  1. Khởi tạo mảng phi[i] = i với mọi \(i\).
  2. Với mỗi số nguyên tố \(p\), duyệt qua mọi bội số \(j\) của \(p\) (\(j = p, 2p, 3p, \dots\)) và cập nhật: \[phi[j] -= phi[j] / p\]
vector<int> sieve_phi(int n) {
    vector<int> phi_arr(n + 1);
    for (int i = 0; i <= n; ++i) phi_arr[i] = i;
    for (int p = 2; p <= n; ++p) {
        if (phi_arr[p] == p) { // p la so nguyen to
            for (int i = p; i <= n; i += p) {
                phi_arr[i] -= phi_arr[i] / p;
            }
        }
    }
    return phi_arr;
}

3. Cài đặt C++17 và Python 3 chuẩn thi đấu

Dưới đây là mã nguồn hoàn chỉnh kết hợp cả hai phương pháp:

Cài đặt C++17

#include <iostream>
#include <vector>

using namespace std;

// Tinh phi(n) trong O(sqrt(n)) bang phan tich thua so nguyen to
long long phi(long long n) {
    long long res = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

// Sang phi ham Euler tu 1 den n trong O(n log log n)
vector<int> sieve_phi(int n) {
    vector<int> phi_arr(n + 1);
    for (int i = 0; i <= n; ++i) phi_arr[i] = i;
    for (int p = 2; p <= n; ++p) {
        if (phi_arr[p] == p) { // p la so nguyen to
            for (int i = p; i <= n; i += p) {
                phi_arr[i] -= phi_arr[i] / p;
            }
        }
    }
    return phi_arr;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Tinh phi(36) = 12
    cout << phi(36) << '\n';
    // Tinh phi(10^9+7) = 10^9+6 (so nguyen to)
    cout << phi(1000000007LL) << '\n';
    
    // Sang phi tu 1 den 12
    auto arr = sieve_phi(12);
    for (int i = 1; i <= 12; ++i) {
        cout << arr[i] << (i == 12 ? '\n' : ' ');
    }
    
    return 0;
}

Cài đặt Python 3

import sys

def phi(n: int) -> int:
    res = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res -= res // p
        p += 1
    if n > 1:
        res -= res // n
    return res

def sieve_phi(n: int) -> list[int]:
    phi_arr = list(range(n + 1))
    for p in range(2, n + 1):
        if phi_arr[p] == p:
            for i in range(p, n + 1, p):
                phi_arr[i] -= phi_arr[i] // p
    return phi_arr

def main():
    print(phi(36))
    print(phi(1000000007))
    arr = sieve_phi(12)
    print(*(arr[1:13]))

if __name__ == '__main__':
    main()

4. Ứng dụng đột phá: Định lý Euler và Rút gọn số mũ

Định lý Euler (Euler's Totient Theorem)

Nếu hai số nguyên \(a\) và \(m\) nguyên tố cùng nhau (\(\gcd(a, m) = 1\)), thì: \[a^{\phi(m)} \equiv 1 \pmod m\]

Hệ quả trực tiếp là khi tính \(a^b \pmod m\), ta có thể rút gọn số mũ \(b\) khổng lồ bằng phép chia lấy dư cho \(\phi(m)\): \[a^b \equiv a^{b \pmod{\phi(m)}} \pmod m\]

Định lý Euler mở rộng (Power Reduction khi không nguyên tố cùng nhau)

Nếu \(\gcd(a, m) > 1\), định lý Euler vẫn có dạng mở rộng cực kỳ hữu ích: \[a^b \equiv a^{(b \pmod{\phi(m)}) + \phi(m)} \pmod m\] với mọi \(b \ge \phi(m)\).

Công thức này là chìa khóa để giải quyết các bài toán Lũy thừa tầng (Power Towers): \[A^{B^{C^D}} \pmod M\] Ta đệ quy tính số mũ tầng trên theo modulo \(\phi(M)\), rồi lại đệ quy tiếp theo \(\phi(\phi(M))\), cho đến khi modulo giảm về 1 thì dừng lại!

Bảng chạy tay chi tiết thuật toán Sàng Phi hàm Euler

Để hiểu rõ cơ chế hoạt động của thuật toán sàng Phi hàm Euler trong đoạn \([1, 12]\), ta theo dõi cách các giá trị \(\phi(i)\) được biến đổi liên tục: Ban đầu, khởi tạo mảng phi[i] = i với mọi \(i \in [1, 12]\).

Bước duyệt số \(i\) Loại số Hành động cập nhật các bội số \(j = i, 2i, 3i, \dots\) Trạng thái mảng phi sau bước duyệt
Khởi tạo - phi[i] = i [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
\(i = 2\) Nguyên tố Nhân \((1 - 1/2) = 1/2\) cho \(j \in \{2, 4, 6, 8, 10, 12\}\) [0, 1, 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6]
\(i = 3\) Nguyên tố Nhân \((1 - 1/3) = 2/3\) cho \(j \in \{3, 6, 9, 12\}\) [0, 1, 1, 2, 2, 5, 2, 7, 4, 6, 5, 11, 4]
\(i = 4\) Hợp số Bỏ qua (vì phi[4] = 2 != 4, đã được số 2 cập nhật) Giữ nguyên
\(i = 5\) Nguyên tố Nhân \((1 - 1/5) = 4/5\) cho \(j \in \{5, 10\}\) [0, 1, 1, 2, 2, 4, 2, 7, 4, 6, 4, 11, 4]
\(i = 7\) Nguyên tố Nhân \((1 - 1/7) = 6/7\) cho \(j \in \{7\}\) [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 11, 4]
\(i = 11\) Nguyên tố Nhân \((1 - 1/11) = 10/11\) cho \(j \in \{11\}\) [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]

Kết quả thu được: \(\phi(12) = 4\) (các số nguyên tố cùng nhau với 12 là \(\{1, 5, 7, 11\}\)), \(\phi(10) = 4\) (\(\{1, 3, 7, 9\}\)), \(\phi(9) = 6\). Toàn bộ mảng từ 1 đến 12 đều chính xác tuyệt đối.

Bốn ứng dụng và lưu ý sống còn trong lập trình thi đấu

  1. Thuật toán tính lũy thừa tầng (Power Tower): Khi tính \(A^{B^C} \pmod M\), ta không thể lấy \(B^C \pmod M\). Theo định lý Euler mở rộng, số mũ ở tầng trên phải được chia lấy dư cho \(\phi(M)\): \[A^X \equiv A^{(X \bmod \phi(M)) + \phi(M)} \pmod M\] với \(X \ge \phi(M)\). Kỹ thuật đệ quy giảm số mũ bằng phi hàm Euler là cách giải tiêu chuẩn cho bài toán lũy thừa tầng trong các kỳ thi Olympic.

  2. Đẳng thức Gauss và bài toán đếm phân số: Đẳng thức \(\sum_{d | n} \phi(d) = n\) là nền tảng để đếm số phân số tối giản trong đoạn \([0, 1]\) có mẫu số không vượt quá \(N\), còn được biết đến với tên gọi Dãy Farey bậc \(N\). Độ dài dãy Farey chính là \(1 + \sum_{i=1}^N \phi(i)\).

  3. Tránh chia số thực gây sai số: Khi cài đặt công thức \(\phi(n) = n \cdot (1 - 1/p)\), không bao giờ dùng phép chia số thực ans *= (1.0 - 1.0 / p). Luôn tính bằng phép toán số nguyên: ans -= ans / p. Cách viết này vừa tránh sai số dấu phẩy động (precision error), vừa chạy nhanh hơn.

  4. Xử lý số nguyên tố lớn hơn căn bậc hai: Sau khi đã chia hết cho mọi ước nguyên tố nhỏ hơn hoặc bằng \(\sqrt{N}\), nếu giá trị \(N\) còn lại vẫn lớn hơn 1, thì phần còn lại chắc chắn là một số nguyên tố cuối cùng. Cần cập nhật ans -= ans / n một lần nữa trước khi trả về kết quả.

Luyện ngay trên Big-O Coding

Để nắm vững cách ứng dụng phi hàm Euler vào các bài toán số học chuyên sâu, bạn hãy luyện tập ngay các bài tập sau:

Đẳng thức Gauss tổng các phi(d) với d chia hết n có ý nghĩa gì?

Đẳng thức này phát biểu rằng tổng giá trị phi hàm Euler của tất cả các ước số nguyên dương của \(n\) đúng bằng \(n\). Ý nghĩa trực quan của nó là phân hoạch tập các phân số \(\{\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}\}\) về dạng tối giản \(\frac{a}{d}\) với \(\gcd(a, d) = 1\). Số lượng phân số có mẫu số tối giản \(d\) đúng bằng \(\phi(d)\), và tổng số lượng mọi phân số bằng \(n\).

Sàng phi hàm Euler tuyến tính O(N) có nhanh hơn sàng O(N log log N) không?

Sàng tuyến tính sử dụng mảng ước nguyên tố nhỏ nhất (Linear Sieve) chỉ duyệt qua mỗi hợp số đúng một lần, đạt độ phức tạp chính xác \(O(N)\). Mặc dù về lý thuyết nhanh hơn, nhưng sàng \(O(N \log \log N)\) trình bày ở trên có bộ nhớ gọn hơn, dễ nhớ và tuy chậm hơn sàng tuyến tính khoảng 3 lần nhưng vẫn đủ nhanh cho các bài thi \(N \le 10^7\) (đo bằng g++ -O2 với \(N = 10^7\): khoảng 0.15 đến 0.2 giây, so với 0.05 đến 0.09 giây của sàng tuyến tính).

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483