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

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

11689번: GCD(n, k) = 1

 

 

풀이

GCD(n, k) = 1을 만족하는 자연수란 n과 k가 서로소 관계에 있다는 뜻입니다.

그래서 1부터 n사이에 n과 서로소인 개수를 구하는 공식은 오일러 피 함수가 있으므로 이 공식을 이용하여 개수를 찾아주면 되는 문제입니다.

 

자세한 설명은 https://ohgym.tistory.com/14 나 https://blog.chodaeho.com/posts/2021/eulers-totient-function/ 블로그를 참조하면 됩니다.

 

 

 

코드

n = int(input())
ans = n
i = 2
while i ** 2 <= n:
    if n % i == 0:
        ans *= (1 - (1/i))
        while not n % i: n //= i
    i += 1
if n > 1: ans *= 1 - 1 / n
print(round(ans))