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

import sys
input = sys.stdin.readline
from math import sqrt

N = int(input())

root = int(sqrt(N))
rootroot = int(sqrt(root))
sieve = {i:1 for i in range(1,root+1)}
prime = []
for i in range(2,root+1):
  if sieve[i] == 0:
    continue
  prime.append(i)
  if i > rootroot:
    continue
  n = 2
  while i*n <= root:
    sieve[i*n] = 0
    n += 1

l = len(prime)
degree = [0]*l

for i in range(l):
  p = prime[i]
  while N%p==0:
    N //= p
    degree[i] += 1

result = 1
for i in range(l):
  if degree[i]:
    p,k = prime[i],degree[i]
    result *= (p-1)*p**(k-1)

if N != 1:
  result *= N-1

print(result)

 

오일러 피 함수에 대한 문제이다.

오일러 피 함수에 대한 배경지식이 있어야 풀 수 있다.

 

알고리즘 과정은

1. N의 제곱근까지의 소수를 구한다.

2. 소인수 분해를 하고 각 소인수의 차수를 구한다.

3. 소인수 분해를 하고 난 N이 1이 아니라면 N은 소수이다.

4. 소인수 분해 결과를 토대로 오일러 파이 함수 공식을 이용해 결과를 출력한다.

 

오릴러 피 함수의 성질은 오일러 피 함수 - 나무위키 (namu.wiki) 이곳을 참고하였다.

 

처음 들어보는 개념이었지만 분명 다른 곳에 쓸모가 있을테니 나중에 활용할 수 있도록 해야겠다.

 

오늘의 교훈) 오일러 피 함수를 다른 문제에서 활용해보자