7546번 - 소수의 주기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 17 | 9 | 9 | 75.000% |
문제
선영이는 계산기가 없으면 두 수의 나눗셈을 계산할 수 없다. 선영이는 다가오는 시험을 대비하기 위해 나눗셈을 계산해보려고 한다. 이번 시험에는 \(b\)진법으로 나타낸 두 수를 나눴을 때, 주기의 길이를 구하는 문제가 나온다. 선영이는 자신이 손으로 계산한 결과가 정답과 맞는지를 확인하는 프로그램을 작성하려고 한다.
진법 \(b\), 분자 \(x\), 분모 \(y\)가 주어진다. \(x\)와 \(y\)는 모두 \(b\)진법으로 나타낸 수이다. \(b\)진법 수 \(q = \frac {x} {y}\)의 주기를 구하는 프로그램을 작성하시오. 유리수 \(q\)를 b진법으로 나타내는 방법은 다음과 같다.
\(q=q_{n}q_{n-1}\dots q_{0}.q_{-1}q_{-2} \dots = \sum _{i=-\infty } ^{n}{q_ib^i}\)
아래는 예이다.
\(\frac {1_{10}}{2_{10}} = 0.5_{10}\), \(\frac {1_3} {10_3} = 0.1_3\), \(\frac {2_{10}}{11_{10}} = 0.181818\dots_{10} = 0.\overline { 18 } _{10}\)
위의 처음 두 예제는 유한 소수이다. 따라서, 주기의 길이는 0이다. 첫 번째 예제의 경우에 주기의 길이가 1인 \(0.4\overline { 9 } _{ 10 }\)로 나타낼 수 있지만, 이 문제에서 그러한 경우는 신경쓰지 않는다.
세 번째 예제의 경우 주기의 길이는 2이다.
입력
첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, \(b\), \(x\), \(y\)가 주어진다. (2 ≤ \(b\) ≤ 36, 0 < \(y\) ≤ 10000010) 0부터 9까지 숫자로 나타낼 수 없는 자리는 'a'와 'A'로 시작하는 글자로 나타낸다. 이때, 대소문자는 구별하지 않는다.
출력
각 테스트 케이스마다 "Scenario #i:"를 출력한 다음에, 주기의 길이를 출력한다. 각 테스트 케이스 사이에는 빈 칸을 하나 출력한다.
예제 입력 1
4 10 1 2 3 1 10 10 2 11 36 HI ho
예제 출력 1
Scenario #1: 0 Scenario #2: 0 Scenario #3: 2 Scenario #4: 13
출처
University > Tu-Darmstadt Programming Contest > TUD Contest 2004 3번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호