직장인의 개발 일기

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

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다!

https://rudalsd.tistory.com/59?category=1064608 

위의 공식을 이용하여 ans에 n을 대입한 후 n에 대하여 어떠한 수 i로 나누어지면 ans = ans - ans / i를 통해서 답을 구할 수 있습니다.

이때 i * i <= n까지 구하는 이유는 n의 제곱근은 i보다 작거나 같기때문입니다.

하지만 마지막에 n이 1이 아니라면 남은 n은 소수이므로 n이 1이 아닐 때 마지막으로 ans = ans - ans / n을 해주면 답을 구할 수 있습니다.

[ 소스 코드 ]

오일러 피(파이) 함수(Euler's phi function)는 1부터 n까지의 정수 중 n과 서로소인 수의 개수를 구하는 함수이고, Ф(n)으로 표현합니다.

이때, 서로소는  1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수를 말합니다. 이를테면 7과 13은 서로소입니다.

[ 동작 원리 ]

1. p가 소수인 경우

ϕ(p) = p - 1

소수인 경우 약수는 1과 자기 자신밖에 없으므로 자기 자신을 제외한 서로소의 개수는 p - 1입니다.

2. 소수 p의 거듭제곱인 경우

ϕ(p^k) = p^{k - 1}(p - 1)

소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우입니다. p, 2p, 3p... p^{k - 1} * p 즉, p^{k - 1}개가 있습니다. 따라서 ϕ(p^k) 의 개수는 p^{k - 1}(p - 1)입니다.

3. a와 b가 서로소일 때

ϕ(ab) = ϕ(a)ϕ(b)

Ф(ab)는 1부터 ab - 1까지의 수 중에서 ab와 나누어 떨어지는 숫자를 세어보면 a는 b - 1개만큼, b는 a - 1개만큼 있습니다.

따라서,

ϕ(ab) = (ab - 1) - (a + b - 2)

= ab - a - b + 1

= (a - 1)(b - 1) 

= ϕ(a)ϕ(b)      

이 됩니다.

마지막으로 유도한 식들을 바탕으로 임의의 양의 정수 n에 대해 Ф(n)을 구해보겠습니다.

$n = p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdot \cdot p_{n}^{k_{n}}$으로 나타낼 수 있습니다.

따라서,

$\phi (n) = \phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})\phi (p_{3}^{k_{3}})\cdot \cdot \cdot \phi (p_{n}^{k_{n}})$

             $=p_{1}^{k_{1}}(1 - \frac{1}{p_{1}})p_{2}^{k_{2}}(1 - \frac{1}{p_{2}})p_{3}^{k_{3}}(1 - \frac{1}{p_{3}})\cdot \cdot \cdot p_{n}^{k_{n}}(1 - \frac{1}{p_{n}})$

             $=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\cdot \cdot \cdot p_{n}^{k_{n}} (1 - \frac{1}{p_{1}})(1 - \frac{1}{p_{2}})(1 - \frac{1}{p_{3}})\cdot \cdot \cdot (1 - \frac{1}{p_{n}})$

             $=n(1 - \frac{1}{p_{1}})(1 - \frac{1}{p_{2}})(1 - \frac{1}{p_{3}})\cdot \cdot \cdot (1 - \frac{1}{p_{n}})$

이 됩니다.

이렇게 $\phi (n)$ 을 1부터 n - 1까지의 모든 숫자에 대해 최대공약수를 구할 필요 없이 깔끔하게 구할 수 있습니다.