[Python] 백준 11689 GCD(n, k) = 1

문제 링크 : https://www.acmicpc.net/problem/

1. 문제 설명

어떤 수가 주어지면, 그 수의 약수를 구하거나 찾거나 활용해야 한다. 대부분의 경우, 그리고 코딩 테스트에 등장하는 문제는 에라토스테네스의 체를 활용하는 정도인데, 백준에서는 그 이상의 지식이 필요한 문제가 종종 있다. 이 문제도 결론을 먼저 말하자면, 오일러 피 함수를 사용해야 한다.

2. 문제 풀이

풀이 코드 : Python

우선 오일러 피 함수를 알아보자. 오일러 피 함수는, 어떤 정수가 주어졌을 때, 그 정수보다 더 작은 수 중에서 서로소인 수의 개수를 알아낼 수 있는 함수이다.

함수는 다음과 같이 계산할 수 있고, 이 값을 계산하기 위해서는 n의 약수가되는 소수를 발견해야 한다.

for i in range(2, int(n**0.5) + 1):
    if not n % i:
        pass

다행히도 n이 주어졌을때, 나누어 떨어지는 수를 찾는 것은 어렵지 않다. 그중에서 소수만 찾아야 하는데, 나누어 떨어지는 최대 소수는 그 수의 제곱근까지만 탐색하면 된다.

for i in range(2, int(n**0.5) + 1):
    if not n % i:
        while not n % i:
            n //= i

모든 약수를 찾는 것이 아니라, 소수만 찾는 것이므로 약수를 처음 발견하면 나누어 떨어지는 동안 나누어준다. 예를 들어 20이 주어졌을 때, 2로 나누어 떨어지는데, 2의 배수중 하나인 4가 20의 약수가 된다. 이를 추가적으로 탐색하지 않기 위해 2로 계속 나누어준다. 그러면 5가 되고, 추가적인 탐색을 이어간다.
그러면 20의 약수중 소수만 발견할 수 있고, 2, 5를 찾게 된다. 그 다음으로는 오일러 피 함수를 적용해서 계산할 수 있다.

ans = n
for i in range(2, int(n**0.5) + 1):
    if not n % i:
        ans = (ans // i) * (i - 1)
        while not n % i:
            n //= i
print(ans if n == 1 else (ans // n) * (n - 1))

그래서 다음과 같이 처음에는 주어진 n을 정답으로 설정한 후, 원하는 소수를 찾을 때마다 연산을 진행한다. 물론 소수를 다 찾은 후 정답을 계산해도 되지만, 추가적 메모리, 시간이 필요하게 되어 for문 하나로 해결할 수 있도록 했다.
하지만 여기서 마무리하면 안되는데, n자체가 소수이면 정답은 n으로 남게 된다. 하지만 어떤 소수가 주어졌을 때, 문제의 정답은 n-1이 되어 추가적인 조건문을 한 번 더 실행한다.