Euler's Totient Function | Hàm Phi Euler - Tutorial SPOJ

Nếu $p$ là số nguyên tố và $k \ge 1$, thì có $\frac{p^k}{p} = p^{k-1}$ số từ $1..p^k$ chia hết cho $p$. Do đó ta có $\phi(p^k) = p^k - p^{k-1}$.

Nếu $a$ và $b$ nguyên tố cùng nhau, hay $gcd(a,b) = 1$, ta có $\phi(a b) = \phi(a) \cdot \phi(b)$. Tính chất này không phải dễ dàng để nhận thấy. Dựa trên Định lý phần dư Trung Hoa, với mỗi $0 \le x < a$ và $0 \le y < b$ thì sẽ tồn tại 1 số $0 \le z < a b$ thoả $z \equiv x \pmod{a}$ và $z \equiv y \pmod{b}$. Dễ thấy $z$ nguyên tố cùng nhau với $a b$ nếu và chỉ nếu $x$ nguyên tố cùng nhau với $a$ và $y$ nguyên tố cùng nhau với $b$. Do đó số lượng số nguyên tố cùng nhau với $a b$ là tích của 2 thành phần $a$ và $b$ hay $\phi(a b) = \phi(a) \cdot \phi(b)$.

Đối với $a$ và $b$ không nguyên tố cùng nhau, $\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$ với $d = \gcd(a, b)$.

Dựa trên 3 tính chất đầu tiên, ta có thể tính được $\phi(n)$ thông qua việc phân tích thừa số nguyên tố $n$. Cụ thể nếu \[n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}\]

với $p_i$ là thừa số nguyên tố thứ $i$ của $n$.

Khi đó ta có: \[\begin{align} \phi (n) &= \phi ({p_1}^{a_1}) \cdot \phi ({p_2}^{a_2}) \cdots \phi ({p_k}^{a_k}) \\\\ &= \left({p_1}^{a_1} - {p_1}^{a_1 - 1}\right) \cdot \left({p_2}^{a_2} - {p_2}^{a_2 - 1}\right) \cdots \left({p_k}^{a_k} - {p_k}^{a_k - 1}\right) \\\\ &= p_1^{a_1} \cdot \left(1 - \frac{1}{p_1}\right) \cdot p_2^{a_2} \cdot \left(1 - \frac{1}{p_2}\right) \cdots p_k^{a_k} \cdot \left(1 - \frac{1}{p_k}\right) \\\\ &= n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \end{align}\]

Implementation

Độ phức tạp của phép phân tích thừa số nguyên tố của số nguyên $n$ là trong $O(\sqrt{n})$. Do đố độ phức tạp của hàm $\phi (n)$ cũng là $O(\sqrt{n})$.int phi(int n) { int 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) result -= result / n; return result; }

Tính phi hàm Euler từ $1$ tới $n$ trong $O(n \log\log{n})$

Bài toán đặt ra là tính phi hàm Euler cho mọi số từ $1$ tới $n$. Nếu ta thực hiện giải thuật trên cho từng số trong đoạn $1..n$ thì sẽ không hiệu quả.

Chúng ta sử dụng ý tưởng từ giải thuật sàng Eratos, với độ phức tạp $O(n \log \log n)$.void phi_1_to_n(int n) { vector<int> phi(n + 1); phi[0] = 0; phi[1] = 1; for (int i = 2; i <= n; i++) phi[i] = i; for (int i = 2; i <= n; i++) { if (phi[i] == i) { for (int j = i; j <= n; j += i) phi[j] -= phi[j] / i; } } }

Tính chất tổng hàm phi từ các ước số

Một tính chất thú vị sau từ hàm phi Euler: \[\sum_{d|n} \phi{(d)} = n\]

Ví dụ với $n = 10$, các ước số của $10$ là $1, 2, 5, 10$, khi đó ta có:

$\phi{(1)} + \phi{(2)} + \phi{(5)} + \phi{(10)} = 1 + 1 + 4 + 4 = 10$

Tính phi hàm Euler từ $1$ tới $n$ trong $O(n \log{n})$

Dựa trên tính chất này, ta cũng có giải thuật để tính hàm phi cho mọi số trong đoạn $1,n$ với độ phức tạp cao hơn giải thuật trước, với độ phức tạp $O(n \log n)$.void phi_1_to_n(int n) { vector<int> phi(n + 1); phi[0] = 0; phi[1] = 1; for (int i = 2; i <= n; i++) phi[i] = i - 1; for (int i = 2; i <= n; i++) for (int j = 2 * i; j <= n; j += i) phi[j] -= phi[i]; }

Ứng dụng của hàm phi Euler

Tính chất nổi tiếng và quan trọng nhất của hàm phi Euler được sử dụng trong định lý Euler: \[a^{\phi(m)} \equiv 1 \pmod m\]

với $a$ và $m$ nguyên tố cùng nhau.

Thông thường $m$ là số nguyên tố, khi đó định lý Euler lúc này được đưa về định lý Fermat nhỏ như sau: \[a^{m - 1} \equiv 1 \pmod m\]

Các định lý này thường được sử dụng trong các bài toán thực tế, cụ thể như bài toán tìm nghich đảo module hay modular multiplicative inverse

Practice Problems

• SPOJ #4141 “Euler Totient Function” [Difficulty: CakeWalk]
• UVA #10179 “Irreducible Basic Fractions” [Difficulty: Easy]
• UVA #10299 “Relatives” [Difficulty: Easy]
• UVA #11327 “Enumerating Rational Numbers” [Difficulty: Medium]
• TIMUS #1673 “Admission to Exam” [Difficulty: High]
• UVA 10990 - Another New Function
• Codechef - Golu and Sweetness
• SPOJ - LCM Sum
• GYM - Simple Calculations (F)
• UVA 13132 - Laser Mirrors
• SPOJ - GCDEX
• UVA 12995 - Farey Sequence
• SPOJ - Totient in Permutation (easy)
• LOJ - Mathematically Hard
• SPOJ - Totient Extreme
• SPOJ - Playing with GCD
• SPOJ - G Force
• SPOJ - Smallest Inverse Euler Totient Function
• Codeforces - Power Tower