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

오일러 피 함수의 개념에 관한 문제입니다.

풀이

오일러 피($\phi$) 함수?

오일러 피 함수는 자연수 $N$에 대해 $N$과 서로소인 $N$이하의 자연수의 개수를 구하는 특수함수이다. 정의는 다음과 같다.

$$\phi(N) = \vert {m: 1 \leq m \leq n, gcd(m, n) = 1} \vert$$

오일러 피 함수의 구현

오일러 피 함수는 소인수분해를 통해 구현할 수 있다. 단순히 $2 \cdots \lceil \sqrt{N} \rceil$의 범위 안에 있는 소수 $i$로 $N$을 나누면서, count의 개수를 $i$의 배수의 개수만큼 줄여나가는 방식이다.

• 이 구현에서는 단순히 $2 \cdots \lceil \sqrt{N} \rceil$의 범위 안에 있는 모든 수로 직접 나누어 떨어지는지 판단했지만, 에라토스테네스의 체를 활용해 미리 범위 안의 소수를 계산한 뒤 소수들로만 반복문을 진행해도 됩니다.
• count = count - count / i는
  기존 count 값($i$의 배수를 지우기 전의 서로소의 개수) 에서 count / i ($i$의 배수의 개수)를 빼는 식이다.

from math import sqrt
count = N
for i in range(2, int(sqrt(N)) + 1):
    if N % i == 0:
        count -= count // i     # 오일러 피 함수 계산
        
        while N % i == 0: # 전체 합성수에서 이번에 계산한 소인수를 완전히 제거한다.
            N //= i

if N > 1: # 아직 소인수가 남아있는 경우
    count -= count // N

print(count)

반복문의 범위에 유의하라

처음에는 다음과 같이 $[2,\lceil \sqrt{N} \rceil)$ 까지 반복하며 계산했는데 오답 처리되었다. 한참을 원인을 찾지 못하고 방황하고 있었는데, $\sqrt{N}$ 이 소수인 경우 이 범위에는 포함되지 않아 계산이 잘못됨을 깨달았다.

from math import ceil, sqrt
for i in range(2, ceil(sqrt(N))):
    ...

따라서, $\sqrt{N}$이 범위에 포함되도록 $[2, \lceil \sqrt{N} \rceil + 1)$로 범위를 고쳐서 해결했다.

전체 코드

from math import sqrt
input = open(0).readline
N = int(input())

count = N
for i in range(2, int(sqrt(N)) + 1):
    if N % i == 0:
        count -= count // i     # 오일러 피 함수 계산
        
        while N % i == 0: # 전체 합성수에서 이번에 계산한 소인수를 완전히 제거한다.
            N //= i

if N > 1: # 아직 소인수가 남아있는 경우
    count -= count // N

print(count)