기약분수 > 문제은행

본문 바로가기


실전대비 Level4

1363 : 기약분수

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 12 회    시도횟수: 117 회   



0 초과 1 미만이고 분모와 분자가 K 이하인 자연수인 모든 기약분수를 오름차순으로 나열했다.

 

이 때 분수 a/b가 주어질 때 바로 앞에 위치한 분수와 바로 뒤에 위치한 분수를 구하는 프로그램을 작성하여라.


첫 번째 줄에는 테스트 케이스의 수 T (1≤T≤10)가 주어진다. 두 번째 줄에서 T개의 줄에는 K, a, b (1≤a≤b≤K, 2≤K≤1,000,000,000)가 주어진다.



만약 a/b가 기약분수가 아니라면 "Error"를 출력한다. 그렇지 않으면 a/b 바로 앞의 분수와 바로 뒤의 분수를 "p/q r/s" 꼴로 출력한다.

만약, 앞의 분수나 뒤의 분수가 없다면 "None"을 출력한다.


[Copy]
3
7 3 4
7 1 7
7 4 6
[Copy]
5/7 4/5
None 1/6
Error



예제 설명 K=7일 때, 나열되는 기약분수는 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7 이다.

전체 데이터의 20%는 k≤100 이다. 전체 데이터의 60%는 k≤5,000,000 이다.



출처 : functionx



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.