오일러 피의 누적합
다이아몬드 I의견: 0
오일러 피 함수 \(\varphi(i)\) 는 \(1\) 이상 \(i\) 이하의 정수 중 \(i\) 와 서로소인 수의 개수이다. 양의 정수 \(N\) 이 주어질 때 $$ \Phi(N) = \sum_{i=1}^{N} \varphi(i) $$ 의 값을 구하는 질의를 \(T\) 번 처리하여라.
\(N\) 이 최대 \(2 \times 10^9\) 까지 커지므로, 모든 \(\varphi(i)\) 를 일일이 구해서 더하는 방법으로는 시간 안에 답할 수 없다. 답은 매우 클 수 있으므로 나머지 연산 없이 정확한 정수값을 그대로 출력한다.
\(1 \le T \le 20\)
\(1 \le N \le 2 \times 10^9\)
첫 줄에 질의의 수 \(T\) 가 주어진다.
이어서 \(T\) 개의 줄에 각 질의의 정수 \(N\) 이 하나씩 주어진다.
각 질의마다 \(\Phi(N)\) 의 정확한 정수값을 한 줄에 하나씩 출력한다.
3
1
5
10
1
10
32\(\varphi\): 1,1,2,2,4,2,6,4,6,4. \(\Phi(1)=1\), \(\Phi(5)=1+1+2+2+4=10\), \(\Phi(10)=32\).
2
100
1
3044
1\(\Phi(100)=3044\), \(\Phi(1)=1\).
riseoj 작성
출처 Original
평가 및 의견
오일러 피의 누적합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
오일러 피의 누적합