백준 11689번 자바

1. 문제

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

11689번: GCD(n, k) = 1

 

2. 접근 방식

오일러의 피를 활용해 푸는 문제다.

해당 개념에 대한 설명은 역시 네이버가 잘해준다.

https://terms.naver.com/entry.naver?docId=5668098&cid=60205&categoryId=60205 

오일러의 피 함수

그럼 내가 해야하는 부분은 이 내용을 코드로 옮겨주는 것이다.

 

첫째, 자연수는 소인수 분해가 가능하다. 

둘째, 오일러의 피 함수 결과는 소수를 활용해 풀 수 있다.

 

우선 결과 값을 저장할 변수 temp를 n값으로 초기화 해준다.

2부터(첫 번째 소수) n의 제곱근(n의 제곱근을 넘는 수로 나누어진다면 이미 그전에 나누어졌다)까지 반복을 하며

n값과 i를 나누기했을 때 나머지 값이 0인 경우

temp = temp - (temp/i)를 해준다.

 

예를 들어 temp가 10이고, i가 2인 경우

temp가 10이라는 것은 1~10까지 총 10개의 수를 가지고 있다는 뜻으로 봐야한다.

temp = 10 - (10/2)에서 10/2 = 5 인 부분은 2의 배수가 5개라는 뜻이다.

그러므로 temp = 10 - 5 = 5개 -> 2의 배수를 제거 했을 때 남은 수

 

그 다음 n값을 i를 나눴을 때 나머지가 0일 동안 반복문을 실행해준다. temp가 갯수라면 n은 실제 자연수이기 때문에 소인수분해를 위해 i값을 계속 나눠주는 것이다.

 

계속 진행하다 보면 i값이 4가 되는데 4는 약수가 2*2다. 해당 소인수 분해는 이전에 진행 됐기 때문에 if문의 조건에 맞지 않다. 그렇기 때문에 소수로만 값을 구할 수 있게 된다.

 

3. 구현

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

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

4. 정리

자주 출제되는 유형은 아니라지만 알아두면 여러모로 써먹을 곳이 있을 것 같다. 또 네이버 지식 백과 기준 RSA암호체계에 사용된 함수라고 하니 기본적인 구현과 이해는 해두자.