제곱근 > 문제은행 : 정보올림피아드&알고리즘



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

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP