시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 16 12 70.588%

문제

10진수에 의하면  “6 × 9 = 42” 는 정답이아니다. 하지만 13진수에 의하면 "6(13) × 9(13) = 42(13)" 는 "42(13) = 4 × 131 + 2 × 130 = 54(10)"  임으로 정답이된다.

정수 p, q, r 을 입력받아  p × q = r  을 정답으로 만들어주는 진수 "B" 를 출력하는 프로그램을 만들어라. 

만약 진수 "B" 가 여려개가 나오면 그중 최소값 을 출력하여라. 

예를 들어 p=11, q=11, r=12  이 주어졌을때  ("11(3) = 1 × 31 + 1 × 3= 4(10) 그리고 121(3) = 1 × 32 + 2 × 31+ 1 × 30 = 16(10)"  와 "11(10) × 11(10) =121(10)" ) 3진수와 10진수에서 정답이므로 출력은 3이 된다. 

만약 p × q = r 을 정답으로 만드는 진수 "B" 가 없을시에는 0을 출력한다.

입력

첫 줄에는 T개의 테스트 케이스가 주어지고, 두번째 줄부터 각 줄에는 정수  p,  q,  r  (1 ≤ p, q, r ≤ 1,000,000) 이 한줄에 공백으로 구별하여 주어진다.

출력

각각의 테스트케이스마다  p × q = r  을 정답으로 만드는 진수 "B" 의 최솟값을 출력하여라.  만약 정답으로 만드는 진수 "B" 가 없다면  0 을 출력한다. 

예제 입력

3
6 9 42
11 11 121
2 2 2

예제 출력

13
3
0

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2002 B번

  • 문제를 번역한 사람: loog