gcd(n, k) = 1

n이 10^18 이하로 주어질 때 1 이상 n 이하의 k 중 gcd(n, k) = 1인 개수, 즉 오일러 피 함수 값을 구한다.

어려움8수학정수론구현완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제5

자연수 $n$ 이 주어진다. $1 \le k \le n$ 이면서 $\gcd(n, k) = 1$ 인 자연수 $k$ 가 몇 개인지 구하는 프로그램을 작성하시오. $\gcd(a, b)$ 는 $a$ 와 $b$ 의 최대공약수를 뜻한다.

첫째 줄에 자연수 $n$ ( $1 \le n \le 10^{18}$ )이 주어진다.

첫째 줄에 $\gcd(n, k) = 1$ 을 만족하는 $1 \le k \le n$ 인 자연수 $k$ 의 개수를 출력한다.