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

문제

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

분석

n이 주어질 때, GCD(n, k) = 1 인 자연수(1 <= k <= n)의 개수를 찾는 문제이다. 즉, 서로소의 개수를 구하는 문제다.

문제에서 조건은 n이 최대 10^12이다. 따라서 long으로 입력받는다.
시간을 고려하지 않았을 때, gcd를 구하는 공식을 사용해서 1부터 n 만큼 반복하여 1이 나오는 것들만 센다는 것을 떠올릴 수 있다. 그러나 지금 조건은 O(N)도 1초 안에 통과하지 못하는 상황이다.

이 문제를 풀기 위해서는 오일러 피 함수라는 개념을 알아야한다.
오일러 피 함수는 1부터 n까지 숫자 중에서, n과 서로소인 숫자가 몇 개인지 세는 함수다. 즉, 문제에서 구하고자 하는 값은 오일러 피 함수로 구할 수 있다.
$\phi(n) = n \times \prod_{p|n} (1 - \frac{1}{p})$ 이 수식을 풀어서 설명한다면, n이 소인수 p를 가지고 있다면, n 이하의 수 중 1/p 만큼은 반드시 p의 배수이므로 그 개수만큼 빼주는 것이다. (p라는 소인수로 나뉘면, 1부터 n까지 p의 배수는 n과 서로소가 될 수 없으므로 빼준다는 의미다.)

이걸 코드로 옮기면, 처음 시작은 전체 개수 n에서 시작한다.
나뉘는 소인수를 찾기 위해 2부터 √n까지 진행한다. 여기서 i를 int로 선언해버리면 중간에 overflow가 나서 무한 반복을 돌 수도 있다. 또한 root까지 진행하는 이유는 작은 소인수들을 먼저 다 처리해서 n을 최대한 나누고 나면, 남아있는 n이 1이거나, 루트보다 큰 딱 하나의 소인수만 남기 때문에 불필요하게 n까지 진행할 필요가 없다. (루트보다 큰 두 소인수는 곱하면 무조건 n을 넘는다.)
그러다가 소인수를 찾으면 배수의 개수를 빼준다. 그리고 n에 해당 소인수를 전부 나눠서 없앤다.
반복문을 다 돌았는데도 n > 1이라면, 그 자체로 가장 큰 소인수이므로 똑같이 계산해 준다.

반복문이 √N 만큼 진행하기 때문에 O(√N)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long cnt = n;
		for (long i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				cnt -= cnt / i;
				while (n % i == 0)
					n /= i;
			}
		}
		if (n > 1)
			cnt -= cnt / n;
		System.out.println(cnt);
		br.close();
	}

}