시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 23 19 73.077%

문제

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+MDxcL3N1cD4mbmJzcDs9IDU0PHN1Yj4oMTApPFwvc3ViPiZxdW90OyZuYnNwOyZuYnNwO1x1Yzc4NFx1YzczY1x1Yjg1YyBcdWM4MTVcdWIyZjVcdWM3NzRcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBwLCZuYnNwO3EsJm5ic3A7ciBcdWM3NDQgXHVjNzg1XHViODI1XHViYzFiXHVjNTQ0Jm5ic3A7Jm5ic3A7cCAmdGltZXM7IHEgPSByICZuYnNwO1x1Yzc0NCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOGZjXHViMjk0IFx1YzljNFx1YzIxOCZuYnNwOyZxdW90O0ImcXVvdDsmbmJzcDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWM5YzRcdWMyMTgmbmJzcDsmcXVvdDtCJnF1b3Q7Jm5ic3A7XHVhYzAwIFx1YzVlY1x1YjgyNFx1YWMxY1x1YWMwMCBcdWIwOThcdWM2MjRcdWJhNzQgXHVhZGY4XHVjOTExIFx1Y2Q1Y1x1YzE5Zlx1YWMxMiZuYnNwO1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgcD0xMSwmbmJzcDtxPTExLCZuYnNwO3I9MTIgJm5ic3A7XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YyAmbmJzcDsoJnF1b3Q7MTE8c3ViPigzKSZuYnNwOzxcL3N1Yj49IDEgJnRpbWVzOyAzPHN1cD4xPFwvc3VwPiZuYnNwOysgMSAmdGltZXM7IDM8c3VwPjAmbmJzcDs8XC9zdXA+PSA0PHN1Yj4oMTApPFwvc3ViPiZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCZuYnNwOzEyMTxzdWI+KDMpJm5ic3A7PFwvc3ViPj0gMSAmdGltZXM7IDM8c3VwPjI8XC9zdXA+Jm5ic3A7KyAyICZ0aW1lczsgMzxzdXA+MTxcL3N1cD4rIDEgJnRpbWVzOyAzPHN1cD4wPFwvc3VwPiZuYnNwOz0gMTY8c3ViPigxMCk8XC9zdWI+JnF1b3Q7Jm5ic3A7Jm5ic3A7XHVjNjQwICZxdW90OzExPHN1Yj4oMTApPFwvc3ViPiZuYnNwOyZ0aW1lczsgMTE8c3ViPigxMCkgPFwvc3ViPj0xMjE8c3ViPigxMCk8XC9zdWI+JnF1b3Q7ICkgM1x1YzljNFx1YzIxOFx1YzY0MCAxMFx1YzljNFx1YzIxOFx1YzVkMFx1YzExYyBcdWM4MTVcdWIyZjVcdWM3NzRcdWJiYzBcdWI4NWMgXHVjZDljXHViODI1XHVjNzQwIDNcdWM3NzQgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QmbmJzcDtwICZ0aW1lczsgcSA9IHIgXHVjNzQ0IFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWM0XHVjMjE4ICZxdW90O0ImcXVvdDsgXHVhYzAwIFx1YzVjNlx1Yzc0NFx1YzJkY1x1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTgmbmJzcDsgcCwgJm5ic3A7cSwgJm5ic3A7ciAmbmJzcDsoMSAmbGU7IHAsIHEsIHIgJmxlOyAxLDAwMCwwMDApJm5ic3A7XHVjNzc0IFx1ZDU1Y1x1YzkwNFx1YzVkMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViY2M0XHVkNTU4XHVjNWVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0Jm5ic3A7Jm5ic3A7cCAmdGltZXM7IHEgPSByICZuYnNwO1x1Yzc0NCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IFx1YzljNFx1YzIxOCZuYnNwOyZxdW90O0ImcXVvdDsmbmJzcDtcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy4gJm5ic3A7XHViOWNjXHVjNTdkIFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjOWM0XHVjMjE4ICZxdW90O0ImcXVvdDsmbmJzcDtcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0Jm5ic3A7Jm5ic3A7MCZuYnNwO1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzIzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11bHRpcGx5IiwiZGVzY3JpcHRpb24iOiI8cD4mbGRxdW87NiAmdGltZXM7IDkgPSA0MiZyZHF1bzsgaXMgbm90IHRydWUgZm9yIGJhc2UgMTAsIGJ1dCBpcyB0cnVlIGZvciBiYXNlIDEzLiBUaGF0IGlzLCA2PHN1Yj4oMTMpPFwvc3ViPiAmdGltZXM7IDk8c3ViPigxMyk8XC9zdWI+ID0gNDI8c3ViPigxMyk8XC9zdWI+IGJlY2F1c2UgNDI8c3ViPigxMyk8XC9zdWI+ID0gNCAmdGltZXM7IDEzPHN1cD4xPFwvc3VwPiArIDIgJnRpbWVzOyAxMzxzdXA+MDxcL3N1cD4gPSA1NDxzdWI+KDEwKTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGlucHV0cyB0aHJlZSBpbnRlZ2VycyBwLCBxLCBhbmQgciBhbmQgZGV0ZXJtaW5lcyB0aGUgYmFzZSBCICgyICZsZTsgQiAmbGU7IDE2KSBmb3Igd2hpY2ggcCAmdGltZXM7IHEgPSByLiBJZiB0aGVyZSBhcmUgbWFueSBjYW5kaWRhdGVzIGZvciBCLCBvdXRwdXQgdGhlIHNtYWxsZXN0IG9uZS4gRm9yIGV4YW1wbGUsIGxldCBwID0gMTEsIHEgPSAxMSwgYW5kIHIgPSAxMjEuIFRoZW4gd2UgaGF2ZSAxMTxzdWI+KDMpPFwvc3ViPiAmdGltZXM7IDExPHN1Yj4oMyk8XC9zdWI+ID0gMTIxPHN1Yj4oMyk8XC9zdWI+IGJlY2F1c2UgMTE8c3ViPigzKTxcL3N1Yj4gPSAxICZ0aW1lczsgMzxzdXA+MTxcL3N1cD4gKyAxICZ0aW1lczsgMzxzdXA+MDxcL3N1cD4gPSA0PHN1Yj4oMTApPFwvc3ViPiBhbmQgMTIxPHN1Yj4oMyk8XC9zdWI+ID0gMSAmdGltZXM7IDM8c3VwPjI8XC9zdXA+ICsgMiAmdGltZXM7IDM8c3VwPjE8XC9zdXA+KyAxICZ0aW1lczsgMzxzdXA+MDxcL3N1cD4gPSAxNjxzdWI+KDEwKTxcL3N1Yj4uIEZvciBhbm90aGVyIGJhc2Ugc3VjaCBhcyAxMCwgd2UgYWxzbyBoYXZlIDExPHN1Yj4oMTApPFwvc3ViPiAmdGltZXM7IDExPHN1Yj4oMTApPFwvc3ViPiA9IDEyMTxzdWI+KDEwKTxcL3N1Yj4uIEluIHRoaXMgY2FzZSwgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgMyB3aGljaCBpcyB0aGUgc21hbGxlc3QgYmFzZS4gSWYgdGhlcmUgaXMgbm8gY2FuZGlkYXRlIGZvciBCLCBvdXRwdXQgMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCApIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0aHJlZSBpbnRlZ2VycyBwLCBxLCBhbmQgciBpbiBhIGxpbmUuIEFsbCBkaWdpdHMgb2YgcCwgcSwgYW5kIHIgYXJlIG51bWVyaWMgZGlnaXRzIGFuZCAxICZsZTsgcCwgcSwgciAmbGU7IDEsMDAwLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgd2hpY2ggaXMgdGhlIHNtYWxsZXN0IGJhc2UgZm9yIHdoaWNoIHAgJnRpbWVzOyBxID0gci4gSWYgdGhlcmUgaXMgbm8gc3VjaCBiYXNlLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCAwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: loog