백준 / 11689 / GCD(n, k) = 1 / 파이썬, python, pypy

 

11689번: GCD(n, k) = 1

 

문제를 처음 봤을 때, 최대공약수(GCD)를 구해서 결과값이 1인 수들의 수만 구하면 될 것이라 생각했다.

 

그러나 입력값의 최댓값이 10^12이므로 시간이 부족할 것이라 생각했고, 

 

에라토스테네스의 체를 사용해서 소수만 구한 뒤, 나누어가면서 오일러 피 함수를 사용하면 될 것이라 생각했다.

 

그러나 10^12개의 리스트를 만들어두면 메모리 에러가 나므로

 

에라토스테네스의 체와 같이 for i in range(2, int(N**0.5) + 1)을 통해 

 

N % i == 0일 경우 아닐때까지 나누어서 배수를 체크 안 하도록 설정하였다.

 

오일러 피 함수를 안다면 쉽게, 모른다면 어떤식으로 풀었을 지 생각이 안나는 문제였다.....

 

=================================================================

오일러 피 함수의 경우

 

위 식과 같이 구할 수 있는데

 

 anwer * (1 - 1/p1) * (1 - 1/p2) * ..... * (1-1/pm)

= (answer - answer / p1) * (1 - 1/p2) * ..... * (1-1/pm)

 

와 같이 구할 수 있으므로 

 

answer -= answer / p1 으로 식을 설정하였다.

=================================================================

 

import sys
 
N = int(sys.stdin.readline())
answer = N
 
for i in range(2, int(N**0.5) + 1):
    if N % i == 0:
        while N % i == 0:
            N //= i
 
        answer -= answer / i
 
if N > 1:
    answer -= answer / N
 
print(int(answer))