[정수론] 백준과 함께 하는 정수론 - 2

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

문제는 간단하다. 자연수 $n$이 주어졌을 때, $GCD(n, k)=1$ 을 만족하는 자연수 $1\leq k\leq n$ 의 개수를 구하면 되는 문제이다.

그냥 단순히 $O(N)$ 으로 반복문을 전부 돌려보며 카운팅을 하면 안되냐 할 수 있겠지만 $n$ 의 제한을 보면 $1\leq n\leq 10^{12}$ 이다. 만약 이 방식으로 제출했다면 채점 현황에 시간초과 가 찍혀 있을 것이다.

이 문제를 해결하기 위해서는 오일러 피(Euler's phi) 함수를 알아야 한다. 이 함수는 정의 자체가 $n$이 양의 정수일 때, $\phi{(n)}$은 $n$과 서로소인 1부터 $n$까지의 정수의 개수와 같다. 문제의 정의와 완전히 일치하는 것이다!

$\phi{(n)}$은 아래와 같다.

$\displaystyle\phi{(n)}=n\prod_{p|n}{(1-\frac{1}{p})}$

$p|n$의 의미는 n은 p의 배수 이다.

결국 위의 식은 $(1-\frac{1}{p})$를 모든 소인수에 대해 곱하고 마지막에 $n$을 곱해주면 된다.

이 문제를 풀면 [BOJ 13926번 gcd(n, k) = 1] 요 문제도 바로 풀어보고 싶을 것이다. 하지만 이거는 소인수를 구하는 부분에서 $O(\sqrt{n})$ 로는 해결이 불가능하고 $O(n^{1/4})$ 의 시간복잡도를 가진 폴라드-로 에 대해 알아야 한다. 또한, 여기서 소수 판정에 대한 최적화까지 이루어져야 하기에 적당히 작은 $n$에 대해 $O(log^3n$)인 밀러-라빈 소수판별법에 대해서도 알아야 한다.

[BOJ 4355번 서로소]

위의 문제와 동일한 문제이고, 1일 때의 출력만 고려해주자.