시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
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 가 공백으로 구분되어 주어진다.
각 테스트 케이스의 답을 한 줄에 출력한다.
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
2 1 2 5 2 8 4 1
예제 1, 2, 3, 4: 본문에서 다루었다.
예제 5, 6: 등차수열을 구성하는 처음 8개의 수를 적어보면 다음과 같다. 2122232425262728... 15번째 숫자는 2, 16번째 숫자는 8이다.
예제 7, 8: 추가 설명 없음.