21397번 - 긴 수 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 66 | 22 | 17 | 31.481% |
문제
Albert는 최근 등차 수열 (arithmetic sequence)에 흥미를 느껴 여러 가지 문제를 만들어보고 있다.
먼저, 임의의 양의 정수 a, b를 고른 후 등차수열 x를 정의한다: xi := a + b * (i-1). 즉, x1 = a 이며 x2 = a+b, x3 = a+b*2, 이런 식으로 무한히 진행된다.
Albert는 별 생각없이 x1, x2, x3, ... 을 공백 없이 (좌측에서 우측으로) 계속 이어 적었는데, 적다 보니 엄청나게 긴 수를 만들어버렸다. 그 와중에 가장 왼쪽에서부터 c 번째에 적힌 숫자는 무엇인지 궁금해졌다.
예를 들어 a = 1, b = 1 인 경우, Albert가 적은 긴 수는 아래와 같다 (등차 수열을 구성하는 처음 21개의 수까지 적었을 경우): 123456789101112131415161718192021...
이 중 좌측에서 15번째 숫자는 "2"가 이고 ("12"의 2) 16번째 숫자는 1이다 ("13"의 1).
다른 예로, a = 3, b = 7 인 경우 긴 수는 아래와 같다 (등차 수열을 구성하는 처음 11개의 수까지 적었을 경우): 310172431384552596673...
이 중 좌측에서 15번째 숫자는 2 이며 ("52"의 2) 16번째 숫자는 5이다 ("59"의 5).
입력으로 a, b, c 가 주어졌을 때, Albert가 등차수열 xi = a + b * (i-1)을 공백없이 연속으로 적었을 경우 c번째 숫자가 무엇인지 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 걸쳐 a, b, c 가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 답을 한 줄에 출력한다.
제한
- 1 ≤ T ≤ 5,000
- 1 ≤ a, b, ≤ 106
- 1 ≤ c ≤ 1012
예제 입력 1
8 1 1 15 1 1 16 3 7 15 3 7 16 21 1 15 21 1 16 4 3 1000000000 400 300 100000000
예제 출력 1
2 1 2 5 2 8 4 1
예제 1, 2, 3, 4: 본문에서 다루었다.
예제 5, 6: 등차수열을 구성하는 처음 8개의 수를 적어보면 다음과 같다. 2122232425262728... 15번째 숫자는 2, 16번째 숫자는 8이다.
예제 7, 8: 추가 설명 없음.
시간 제한
- Java 8: 2 초
- PyPy3: 1.5 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호