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

728x90

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

11689번: GCD(n, k) = 1

---

문제

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

입력

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

출력

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

---

n이 주어졌을 때 n이하의 서로소 개수를 구하면 된다는 뜻이다.

이 문제를 해결하는 기가 막힌 공식이 있다. 오일러 피 함수인데 n이하의 서로소 개수를 구하는 공식이다.

진행 과정은 아래와 같다.

0. n을 정한다.
1. 소인수를 구한다.(소인수를 p라 하자)
2. n에 (1 - 1/p)를 곱한다.

간단하다. 

 

위 공식에 대한 증명은 아래에서 보자. 

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

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

---

코드

n=int(input())
ans = n

for i in range(2, int(n**0.5)+1):
    # i로 나누어 떨어진다면
    if n % i == 0:
        # n이 가지고 있는 i의 개수 만큼 나눠주기
        while n % i == 0:   
            n //= i
        # 오일러 피 함수 
        ans *= (1-1/i)

# 자기 자신이 소수였던 경우
if n>1:
    ans *= (1-1/n)

print(int(ans))