[11689] GCD(n, k) = 1

✔ GCD(n, k) = 1

[백준 11689]

문제 분석하기

문제를 만족하는 자연수의 개수가 오일러 피 함수의 정의이므로 오일러 피 함수를 구현

손으로 풀어보기

1. 서로소의 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언
2. 2 ~ N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result / 소인수) 연산으로 result 값을 업데이트
   • n에서 이 소인수는 나누기 연산으로 삭제함
   • 예) 현재 소인수가 2일 때, 2⁷ * 11 * 13을 11 * 13으로 변경
3. 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수이므로
   result = result - (result / n) 연산으로 result 값을 마지막으로 업데이트한 후 출력

예) n = 15

N	result	result 값 업데이트
15	15	P(현재 수) = 2일 때, N(15) % P(2) != 0이므로 소인수가 아님
15	15	P(현재 수) = 3일때, N(15) % P(3) == 0이므로 소인수이므로 값을 업데이트 15 - (15 / 3)이므로 result를 10으로 업데이트 3¹ * 5일 때 현재 소인수가 3이므로 5로 변경 n = 15 / 3 = 5
5	10	P(현재 수) = 5일때, 현재 N(10)의 제곱근보다 크므로 반복문 종료
5	10	n이 1보다 크므로 5가 마지막 소인수이므로 10 - (10/5)이므로 result를 8로 업데이트

슈도코드 작성하기

n(소인수 표현) result(결괏값)
for(2 ~ n의 제곱근) {
    if(현재 값이 소인수라면) {
        결괏값 = 결괏값 - 결괏값 / 현재값
        n에서 현재 소인수 내역을 제거하기
    }
}
if(n > 1) {
    결괏값 = 결괏값 - 결괏값 / n
}
결괏값 출력하기

코드 구현하기

/**
 * 11689) GCD(n, k) = 1
 */
public class D041_11689 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n(소인수 표현)
        long n = Long.parseLong(br.readLine());
        // result(결괏값)
        long result = n;
        // 제곱근까지만 진행
        for (long p = 2; p <= Math.sqrt(n); p++) {
            // p가 소인수인지 확인
            if (n % p == 0) {
                // 결괏값 = 결괏값 - 결괏값 / 현재값 업데이트
                result = result - result / p;
                // n에서 현재 소인수 내역을 제거하기
                while (n % p == 0) {
                    n /= p;
                }
            }
        }
        // 아직 소인수 구성이 남아 있을 때
        if (n > 1)
            // 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스
            result = result - result / n;
        // 결괏값 출력하기
        System.out.println(result);
    }
}