다이아몬드 IV설명
양의 정수 \(n\)에 대해 오일러 피 함수 \(\varphi(n)\)은 \(1\) 이상 \(n\) 이하의 정수 중 \(n\)과 서로소인 것의 개수이다.
여러 개의 \(n\)이 주어질 때 각각에 대해 \(\varphi(n)\)을 구하여라. \(n\)이 최대 \(10^{18}\)까지로 매우 크므로 단순 시행 나눗셈 소인수분해(\(O(\sqrt{n})\))는 통과할 수 없다.
제약
\(1 \le Q \le 1{,}000\)
\(1 \le n \le 10^{18}\)
입력 형식
첫 줄에 질의의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 정수 \(n\)이 주어진다.
출력 형식
각 \(n\)에 대해 \(\varphi(n)\)의 값을 한 줄에 하나씩 출력한다.
예제 1
입력
3
1
6
12
출력
1
2
4설명
\(\varphi(1)=1\). \(\varphi(6)\): 1,5가 6과 서로소이므로 2. \(\varphi(12)\): 1,5,7,11이 서로소이므로 4.
예제 2
입력
2
999999937
1000000000000
출력
999999936
400000000000설명
\(999999937\)은 소수이므로 \(\varphi = 999999936\). \(10^{12} = 2^{12} \cdot 5^{12}\)이므로 \(\varphi = 10^{12}(1-1/2)(1-1/5) = 400000000000\).
문제 정보
riseoj 작성
출처 Original
태그
