시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29 21 17 70.833%

문제

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 을 출력한다. 

예제 입력 1

3
6 9 42
11 11 121
2 2 2

예제 출력 1

13
3
0

힌트

W3sicHJvYmxlbV9pZCI6IjMyMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJNdWx0aXBseSIsImRlc2NyaXB0aW9uIjoiPHA+MTBcdWM5YzRcdWMyMThcdWM1ZDAgXHVjNzU4XHVkNTU4XHViYTc0ICZuYnNwOyZsZHF1bzs2ICZ0aW1lczsgOSA9IDQyJnJkcXVvOyZuYnNwO1x1YjI5NCBcdWM4MTVcdWIyZjVcdWM3NzRcdWM1NDRcdWIyYzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyAxM1x1YzljNFx1YzIxOFx1YzVkMCBcdWM3NThcdWQ1NThcdWJhNzQgJnF1b3Q7NjxzdWI+KDEzKTxcL3N1Yj4mbmJzcDsmdGltZXM7IDk8c3ViPigxMyk8XC9zdWI+Jm5ic3A7PSA0MjxzdWI+KDEzKTxcL3N1Yj4mcXVvdDsmbmJzcDtcdWIyOTQmbmJzcDsmcXVvdDs0MjxzdWI+KDEzKSZuYnNwOzxcL3N1Yj49IDQgJnRpbWVzOyAxMzxzdXA+MTxcL3N1cD4mbmJzcDsrIDIgJnRpbWVzOyAxMzxzdXA+MDxcL3N1cD4mbmJzcDs9IDU0PHN1Yj4oMTApPFwvc3ViPiZxdW90OyZuYnNwOyZuYnNwO1x1Yzc4NFx1YzczY1x1Yjg1YyBcdWM4MTVcdWIyZjVcdWM3NzRcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBwLCZuYnNwO3EsJm5ic3A7ciBcdWM3NDQgXHVjNzg1XHViODI1XHViYzFiXHVjNTQ0Jm5ic3A7Jm5ic3A7cCAmdGltZXM7IHEgPSByICZuYnNwO1x1Yzc0NCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOGZjXHViMjk0IFx1YzljNFx1YzIxOCZuYnNwOyZxdW90O0ImcXVvdDsmbmJzcDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWM5YzRcdWMyMTgmbmJzcDsmcXVvdDtCJnF1b3Q7Jm5ic3A7XHVhYzAwIFx1YzVlY1x1YjgyNFx1YWMxY1x1YWMwMCBcdWIwOThcdWM2MjRcdWJhNzQgXHVhZGY4XHVjOTExIFx1Y2Q1Y1x1YzE4Y1x1YWMxMiZuYnNwO1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgcD0xMSwmbmJzcDtxPTExLCZuYnNwO3I9MTIgJm5ic3A7XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YyAmbmJzcDsoJnF1b3Q7MTE8c3ViPigzKSZuYnNwOzxcL3N1Yj49IDEgJnRpbWVzOyAzPHN1cD4xPFwvc3VwPiZuYnNwOysgMSAmdGltZXM7IDM8c3VwPjAmbmJzcDs8XC9zdXA+PSA0PHN1Yj4oMTApPFwvc3ViPiZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCZuYnNwOzEyMTxzdWI+KDMpJm5ic3A7PFwvc3ViPj0gMSAmdGltZXM7IDM8c3VwPjI8XC9zdXA+Jm5ic3A7KyAyICZ0aW1lczsgMzxzdXA+MTxcL3N1cD4rIDEgJnRpbWVzOyAzPHN1cD4wPFwvc3VwPiZuYnNwOz0gMTY8c3ViPigxMCk8XC9zdWI+JnF1b3Q7Jm5ic3A7Jm5ic3A7XHVjNjQwICZxdW90OzExPHN1Yj4oMTApPFwvc3ViPiZuYnNwOyZ0aW1lczsgMTE8c3ViPigxMCkgPFwvc3ViPj0xMjE8c3ViPigxMCk8XC9zdWI+JnF1b3Q7ICkgM1x1YzljNFx1YzIxOFx1YzY0MCAxMFx1YzljNFx1YzIxOFx1YzVkMFx1YzExYyBcdWM4MTVcdWIyZjVcdWM3NzRcdWJiYzBcdWI4NWMgXHVjZDljXHViODI1XHVjNzQwIDNcdWM3NzQgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QmbmJzcDtwICZ0aW1lczsgcSA9IHIgXHVjNzQ0IFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWM0XHVjMjE4ICZxdW90O0ImcXVvdDsgXHVhYzAwIFx1YzVjNlx1Yzc0NFx1YzJkY1x1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCZuYnNwOyBwLCAmbmJzcDtxLCAmbmJzcDtyICZuYnNwOygxICZsZTsgcCwgcSwgciAmbGU7IDEsMDAwLDAwMCkmbmJzcDtcdWM3NzQgXHVkNTVjXHVjOTA0XHVjNWQwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJjYzRcdWQ1NThcdWM1ZWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQmbmJzcDsmbmJzcDtwICZ0aW1lczsgcSA9IHIgJm5ic3A7XHVjNzQ0IFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWM0XHVjMjE4Jm5ic3A7JnF1b3Q7QiZxdW90OyZuYnNwO1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLiAmbmJzcDtcdWI5Y2NcdWM1N2QgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWM5YzRcdWMyMTggJnF1b3Q7QiZxdW90OyZuYnNwO1x1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQmbmJzcDsmbmJzcDswJm5ic3A7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTXVsdGlwbHkiLCJkZXNjcmlwdGlvbiI6IjxwPiZsZHF1bzs2ICZ0aW1lczsgOSA9IDQyJnJkcXVvOyBpcyBub3QgdHJ1ZSBmb3IgYmFzZSAxMCwgYnV0IGlzIHRydWUgZm9yIGJhc2UgMTMuIFRoYXQgaXMsIDY8c3ViPigxMyk8XC9zdWI+ICZ0aW1lczsgOTxzdWI+KDEzKTxcL3N1Yj4gPSA0MjxzdWI+KDEzKTxcL3N1Yj4gYmVjYXVzZSA0MjxzdWI+KDEzKTxcL3N1Yj4gPSA0ICZ0aW1lczsgMTM8c3VwPjE8XC9zdXA+ICsgMiAmdGltZXM7IDEzPHN1cD4wPFwvc3VwPiA9IDU0PHN1Yj4oMTApPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2ggaW5wdXRzIHRocmVlIGludGVnZXJzIHAsIHEsIGFuZCByIGFuZCBkZXRlcm1pbmVzIHRoZSBiYXNlIEIgKDIgJmxlOyBCICZsZTsgMTYpIGZvciB3aGljaCBwICZ0aW1lczsgcSA9IHIuIElmIHRoZXJlIGFyZSBtYW55IGNhbmRpZGF0ZXMgZm9yIEIsIG91dHB1dCB0aGUgc21hbGxlc3Qgb25lLiBGb3IgZXhhbXBsZSwgbGV0IHAgPSAxMSwgcSA9IDExLCBhbmQgciA9IDEyMS4gVGhlbiB3ZSBoYXZlIDExPHN1Yj4oMyk8XC9zdWI+ICZ0aW1lczsgMTE8c3ViPigzKTxcL3N1Yj4gPSAxMjE8c3ViPigzKTxcL3N1Yj4gYmVjYXVzZSAxMTxzdWI+KDMpPFwvc3ViPiA9IDEgJnRpbWVzOyAzPHN1cD4xPFwvc3VwPiArIDEgJnRpbWVzOyAzPHN1cD4wPFwvc3VwPiA9IDQ8c3ViPigxMCk8XC9zdWI+IGFuZCAxMjE8c3ViPigzKTxcL3N1Yj4gPSAxICZ0aW1lczsgMzxzdXA+MjxcL3N1cD4gKyAyICZ0aW1lczsgMzxzdXA+MTxcL3N1cD4rIDEgJnRpbWVzOyAzPHN1cD4wPFwvc3VwPiA9IDE2PHN1Yj4oMTApPFwvc3ViPi4gRm9yIGFub3RoZXIgYmFzZSBzdWNoIGFzIDEwLCB3ZSBhbHNvIGhhdmUgMTE8c3ViPigxMCk8XC9zdWI+ICZ0aW1lczsgMTE8c3ViPigxMCk8XC9zdWI+ID0gMTIxPHN1Yj4oMTApPFwvc3ViPi4gSW4gdGhpcyBjYXNlLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCAzIHdoaWNoIGlzIHRoZSBzbWFsbGVzdCBiYXNlLiBJZiB0aGVyZSBpcyBubyBjYW5kaWRhdGUgZm9yIEIsIG91dHB1dCAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUICkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGludGVnZXJzIHAsIHEsIGFuZCByIGluIGEgbGluZS4gQWxsIGRpZ2l0cyBvZiBwLCBxLCBhbmQgciBhcmUgbnVtZXJpYyBkaWdpdHMgYW5kIDEgJmxlOyBwLCBxLCByICZsZTsgMSwwMDAsMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciB3aGljaCBpcyB0aGUgc21hbGxlc3QgYmFzZSBmb3Igd2hpY2ggcCAmdGltZXM7IHEgPSByLiBJZiB0aGVyZSBpcyBubyBzdWNoIGJhc2UsIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: loog