[BOJ]11689. GCD(n,k) = 1

문제:

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력:

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

풀이방법:

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

오일러 피 함수 - 위키백과, 우리 모두의 백과사전

GCD(n,k) = 1 는 n과 k가 서로수임을 의미하는 것이고, n과 서로소인 정수의 갯수를 세는 방법은 정수론에서 오일러 피 함수가 있다. 

오일러 피 함수를 간략히 설명하면 다음과 같다. 오일러 피 함수는 주어진 n의 소인수를 구한 뒤에, 각 소인수들의 (1-1/p)를 구해 n에 곱해주면 서로소의 갯수를 구할 수 있다. 따라서 이 함수를 python으로 구현하여 다음과 같이 계산하도록 한다.

n = int(input())
answer = n
for i in range(2, int(n**0.5)+1):
    if n%i==0:
        while n%i==0:
            n //= i
        answer *= ((i-1)/(i))
if n > 1:
    answer *= 1 - (1 / n)
print(int(answer))

문제링크:

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1