10438번 - 페리 수열의 합 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 131 | 57 | 40 | 42.105% |
문제
양의 정수 N에 대해, (0 < a ≤ b), (1 ≤ b ≤ N) 의 조건을 만족하는 모든 기약분수 a/b와 0/1, 1/1을 오름차순으로 나열한 것을 N번째 페리 수열이라 한다.
예를 들어, 6번째 페리 수열은 아래와 같다.
0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1
N번째 페리 수열의 분모만을 차례대로 써서 만든 아래와 같은 b 수열이 있다.
b[1], b[2], ..., b[K]
이때, 페리 수열의 합이란 i = 1부터 K-1까지 b[i]/b[i+1]의 합을 의미한다.
예를 들어, 6번째 페리 수열의 합은 아래와 같다.
1/6 + 6/5 + 5/4 + 4/3 + 3/5 + 5/2 + 2/5 + 5/3 + 3/4 + 4/5 + 5/6 + 6/1 = 35/2
자연수 N에 대해 N번째 페리 수열의 합을 출력하시오.
입력
첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 10000)
각 테스트 케이스는 테스트 케이스의 번호 T와 문제에서 설명한 N의 값이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 10000)
출력
각 테스트 케이스마다 테스트 케이스의 번호와 페리 수열의 합을 출력한다.
합을 출력할 땐 항상 기약분수여야 하며, 합을 기약분수로 나타냈을 때 분모가 1이라면 분자만 출력한다.
예제 입력 1
4 1 6 2 15 3 57 4 9999
예제 출력 1
1 35/2 2 215/2 3 2999/2 4 91180457/2
힌트
N+1번째 페리 수열에는 N번째 페리 수열의 모든 분수에 N+1과 서로소인 N 이하의 자연수의 개수만큼의 분수가 추가로 들어간다.
출처
ICPC > Regionals > North America > Greater New York Region > 2014 Greater New York Programming Contest H번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호