Đề bài
Phi hàm Euler φ(n) đếm số các số nguyên k với 1 ≤ k ≤ n và gcd(k, n) = 1. Ví dụ, φ(9) = 6, vì 1, 2, 4, 5, 7 và 8 không có ước chung nào (ngoài 1) với 9.
Hãy viết eulers_totient(n).
Đếm lần lượt từng k là quá chậm khi n lên tới 10^12. Thay vào đó, hãy dùng công thức tích: φ(n) = n × (1 − 1/p) với mọi ước nguyên tố p phân biệt của n. Tính toàn bằng số nguyên theo dạng n / p × (p − 1) sẽ tránh được phân số.
Đầu vào
n: Một số nguyên dương.
Đầu ra
Trả về φ(n). Theo định nghĩa, φ(1) = 1.
Ràng buộc
1 ≤ n ≤ 10^12
Ví dụ
Đầu vào:
n = 36
Kết quả mong đợi:
expected = 12
Đầu vào:
long long n = 36;
Kết quả mong đợi:
long long expected = 12;
Đầu vào:
long n = 36;
Kết quả mong đợi:
long expected = 12;
Giải thích
36 = 2² × 3², nên φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.
Đầu vào:
n = 13
Kết quả mong đợi:
expected = 12
Đầu vào:
long long n = 13;
Kết quả mong đợi:
long long expected = 12;
Đầu vào:
long n = 13;
Kết quả mong đợi:
long expected = 12;
Giải thích
13 là số nguyên tố, nên mọi k từ 1 đến 12 đều nguyên tố cùng nhau với nó và φ(13) = 12.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Phân tích n bằng phép chia thử đến √n.
Gợi ý 2
Với mỗi số nguyên tố p phân biệt, thay kết quả bằng result / p × (p − 1); chia trước để giá trị luôn nhỏ.
Gợi ý 3
Nếu sau vòng lặp còn sót một thừa số lớn hơn 1 thì đó cũng là số nguyên tố.
Độ phức tạp mong đợi
thời gian O(√n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.