●문제 출처
●정리(요약)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 2544 889 715 34.392%
문제
오일러는 수학을 정말 좋아해서 하루 종일 수학 공부만 하는 수학쟁이이다.
어느 날 오일러는 수학 공부를 하기 위해서 수학 책을 읽고 있던 중에 오일러 피 함수에 대해서 설명하는 부분을 보게 되었다. 오일러 피 함수는 다음과 같이 설명이 되어 있었다.
오일러 피 함수란 φ(n)으로 표기하며 1부터 n까지의 양의 정수 중에서 n과 서로소인 수의 개수를 나타내는 함수이다.
예를 들면 φ(6)은 1부터 6까지의 수 중 6과 서로소인 수의 개수를 말하는데 이는 1과 5로 두 개가 있으므로 φ(6) = 2이다.
오일러는 책의 내용을 곰곰이 읽던 중 어떤 문제가 떠올랐다. 문제의 내용은 다음과 같다.
어떤 양의 정수 n이 있다고 할 때, xφ(x) = n을 만족하는 양의 정수 x가 존재하는가?
고민에 빠진 오일러를 본 당신은 오일러의 궁금증을 해결해주기 위해서 직접 문제를 풀기로 결심했다. 그러므로 당신은 xφ(x) = n을 만족하는 x를 구하는 프로그램을 작성하면 된다.
T(=5) = A[1] + B[1] + B[2]
= A[1] + A[2] + B[1]
= A[2] + B[3]
= A[2] + A[3] + B[1]
= A[3] + B[1] + B[2]
= A[3] + A[4] + B[3]
= A[4] + B[2]
●코드
import java.io.*;
import java.util.*;
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());
for(long x = 1; x<=Math.sqrt(n) ; x++){
if(n % x == 0){
if(x * phi(x) == n){
System.out.println(x);
return;
}
long y = n / x;
if(y * phi(y) == n){
System.out.println(y);
return;
}
}
}
System.out.println(-1);
}
public static long phi(long num) {
long n = num;
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);
}
return temp;
}
}
●느낀 점
오일러 피를 구하는 함수를 구현하고 n의 약수들을 찾아 오일러 피를 계산해 xφ(x) = n 이 되는 수 x를 구하였다.
long y = n / x; 를 해주는 이유는 n = 36, x = 3 이면 y = 36 / 3 = 12 이 된다.
그래서 검사 3, 12 둘 다 검사하기 떄문에 큰 수의 약수를 찾기 위해서 해주었다.
위에 내용을 안해주어서 틀렸다.
오일러 피 너무 어렵지만 공식을 이해하고 학습해야겠다 생각했다.
