시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 146 37 6 85.714%

문제

작년에 가장 좋아하는 분수를 성공적으로 계산할 수 있었던 키파는 올해 선물로 0과 1이 가득찬 표도 받았겠다 이 수를 이진 전개해 보기로 했습니다.

이진법으로 수를 쭉 적어나가다가 키파는 0보다 1이 훨씬 쓰기 쉽다는 것을 깨달았습니다: 0은 끝을 완벽히 닫아 줘야 하지만, 1은 그럴 필요 없이 쭉 내리기만 하면 되었기 때문입니다!

키파는 이 작업을 질릴 때까지 할 것이기 때문에 이 작업을 무한히 해 나갈 때 쓴 숫자의 개수 중 1의 비율을 최대화하고 싶었습니다. 키파를 위해 이때 1의 비율을 출력하는 프로그램을 작성하세요.

입력

첫 줄에 테스트 케이스의 수 T가 주어집니다.

둘째 줄부터 T개의 줄에 109보다 작거나 같은 두 양의 정수 a, b가 주어집니다. 키파가 이진 전개할 분수가 a/b임을 의미합니다.

출력

T개의 줄에 정답을 기약분수의 형태로 출력합니다. 분자와 분모를 /를 사이에 두고 출력하면 됩니다.

서브태스크 1 (5점)

T = 5, b ≤ 106.

서브태스크 2 (25점)

T = 5, 모든 분수의 소수 표현의 (이진) 순환마디의 길이의 합이 3·109을 넘지 않음.

서브태스크 3 (70점)

T = 10.

예제 입력 1

5
3 18
3 23
5 22
10 27
12 4

예제 출력 1

1/2
4/11
1/2
1/2
1/1

마지막 테스트 케이스의 경우, 12/4를 이진 전개한 값으로 가능한 것 몇 가지를 설명하면,

  • 12/4 = 11(2)는 무한 이진 전개가 아니기에 키파가 질리도록 수를 쓸 수 없습니다. 이런 경우는 고려하면 안 됩니다.
  • 12/4 = 11.000…(2)는 무한 이진 전개이고, 이 이진 전개에서 쓴 1의 비율은 0/1입니다.
  • 12/4 = 10.111…(2) 역시 무한 이진 전개이고, 이 이진 전개에서 쓴 1의 비율은 1/1입니다.

따라서 12/4의 무한 이진 전개 중 1의 비율의 최댓값인 1/1을 출력합니다.

출처

Contest > 키파컵 > 제2회 키파컵 C번

  • 문제를 만든 사람: kipa00

채점

  • 예제는 채점하지 않는다.