알고리즘 챌린지 9일차

문제

문제: 백준 알고리즘 11689번 GCD(n,k) = 1

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); //현재 소인수 구성 (범위가 10^12까지 이므로 long 타입으로 선언)
        long result = n;    //서로소의 개수
        for (int i = 2; i <= Math.sqrt(n); i++) {   //n의 제곱근까지 반복
            if (n % i == 0) {
                result = result - (result / i);     //n보다 작은 값중에 i의 배수의 개수만큼 제거
                while ((n % i) == 0) {  //소인수 구성에서 i를 뺌
                    n = n / i;
                }
            }
        }
        if (n > 1) {    //반복문 종료 후 n이 1보다 크면 n이 마지막 소인수라는 의미이므로 빼줌
            result = result - (result / n);
        }
        System.out.println(result);
        sc.close();
    }
}

풀이

GCD(n,k) = 1을 만족하는 자연수의 개수가 바로 오일러 피 함수의 정의이다.

• 서로소의 개수를 표현하는 result와 현재 소인수 구성을 표시하는 n을 선언한다.
• 오일러 피 핵심 이론을 참고해서 2~N의 제곱근까지 탐색한다.
• 소인수일 때 result = result - (result/소인수) 연산으로 result값을 업데이트한다.
• 이때 n에서 이 소인수를 나누기 연산으로 삭제한다.
• 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수라는 뜻이므로 result = result - (result/n) 연산으로 result값을 마지막으로 업데이트한다.

후기

이 문제는 오일러 피 함수를 알고 있는지 물어보는 정석적인 문제였다. 입력에서 n의 범위가 1 <= n <= 10^12 이므로 long 타입으로 선언해야 한다. 문제의 입력 조건을 잘 확인하자!