Tính hàm phi Euler
Xem PDF
Điểm:
300
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Trong số học, Hàm Euler \(\phi\) của một số nguyên dương \(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\).
Yêu cầu: Cho số nguyên dương \(n\). Tính giá trị của \(\phi(n)\).
Input
-
Dòng thứ nhất chứa số \(t(1 \le t \le 50)\) - Thể hiện số lượng testcase.
-
t dòng tiếp theo, mỗi dòng chứa một số nguyên \(n(1 \le n \le 10^8)\).
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm.
Example
Test 1
Input
5
1
2
3
4
5Output
1
1
2
2
4
Bình luận
Gợi ý
ϕ(\(n\))=\(n\) * (1-1/\(p_1\)) * (1-1/\(p_2\)) * ... * (1-1/\(p_m\)) với \(p\) là các ước nguyên tố riêng biệt của \(n\)
Code
C++: https://ideone.com/WYeCpN
Suggest bản khó hơn với \(N \le 10^{12}\)
bài này cày trâu cx ac mà nên 300 là hơi cao :v
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.