Hướng dẫn giải của Phi Hàm Euler
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Lời giải
Tính lại từ đầu cho mỗi truy vấn bằng cách thử mọi số từ ~1~ đến ~n~ cần tới ~T \times n~ phép tính ước chung lớn nhất, quá chậm.
Hãy sàng trước một bảng ~\varphi~ cho mọi giá trị đến ~10^6~ chỉ một lần, dựa vào công thức ~\varphi(n) = n \prod_{p \mid n} \left(1 - \dfrac{1}{p}\right)~, sau đó mỗi truy vấn chỉ còn là một phép tra bảng.
Bình luận