joomongogo
다이아몬드 IV
★★★★★
2026-06-11 22:05
피 함수 문제
R00639
거대한 수의 오일러 피
레이팅
의견: 1
설명
양의 정수 \(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
태그
평가 및 의견
거대한 수의 오일러 피
개요
티어 투표 분포
다이아몬드 IV
1
Log in to rate problems.
개별 의견
joomongogo
다이아몬드 IV
★★★★★
2026-06-11 22:05
풀이 제출
거대한 수의 오일러 피
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기