1054 : 제곱근
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 9 회
- 시도횟수
- 23 회
문제
소수 p의 제곱근()은 무리수라고 알려져 있다.
무리수는 유리수의 표현 방법 중의 하나인 분수 꼴로 나타내지지 않는 수이다.
하지만 그 수에 어느 정도 가까운 분수 꼴을 찾을 수 있을 것이다.
"가까운 분수"라는 말이 애매하기 때문에 분수 꼴을 나타낼 때 "분수의 분자와 분모에 쓰이는 숫자의 최대값을 자연수 n"으로 제한하기로 한다.
예를 들어 n이 4일 경우에는 의 11가지의 분수들 중에서 찾으면 된다.
의 5가지 분수는 각각
와 같이 약분되기 때문에 고려하지 않는다.
이런 조건을 만족하면서 보다 큰 분수들 중에서
에 가장 가까운 분수와
보다 작은 분수들 중에서
에 가장 가까운 분수를 찾으려고 한다.
예를 들어서 소수 p의 값으로 7이 주어지고 n이 20 이 주어지면
보다 큰 분수 중 가장
에 가까운 수는
이고
보다 작은 분수중에서 가장 가까운 수는
가 된다.
입력형식
파일에는 소수(1≤p≤10,000)와 자연수 n(1≤n≤10,000)이 들어 있다.
n은 p에 대해 답을 구할수 있도록 충분히 크게 주어진다고 가정한다.
출력형식
첫번째 줄에는 보다 큰 분수들 중에서
에 가장 가까운 분수의 분자와 분모를 차례로 출력한다.
마찬가지로 두 번째 줄에는 보다 작은 분수들 중에서
에 가장 가까운 분수의 분자와 분모를 출력한다.
입력 예7 20 |
출력 예8 3 13 5 |