#B2141. 确定进制

确定进制

题目描述

6×9=426 \times 9=42 对于十进制来说是错误的,但是对于 1313 进制来说是正确的。即 6(13)×9(13)=42(13)6_{(13)} \times 9_{(13)}=42_{(13)},而 42(13)=4×131+2×130=54(10)42_{(13)}=4 \times 13^1+2 \times 13^0=54_{(10)}

你的任务是写一段程序读入三个整数 p,qp,qrr,然后确定一个进制 B(2B16)B(2 \le B \le 16) 使得 p×q=rp\times q=r。如果 BB 有很多选择,则输出最小的一个。

例如:p=11,q=11,r=121p=11,q=11,r=121,则有 11(3)×11(3)=121(3)11_{(3)} \times 11_{(3)}=121_{(3)},因为 11(3)=1×31+1×30=4(10)11_{(3)}=1 \times 3^1+1 \times 3^0=4_{(10)} 和 $121_{(3)}=1 \times 3^2+2 \times 3^1+1 \times 3^0=16_{(10)}$。对于进制 10,10,11(10)×11(10)=121(10)11_{(10)} \times 11_{(10)}=121_{(10)}。这种情况下,应该输出 33。如果没有合适的进制,则输出 00

输入格式

一行,包含三个整数 p,q,rp,q,r,相邻两个整数之间用单个空格隔开。

输出格式

一个整数:即使得 p×q=rp \times q=r 成立的最小的 BB。如果没有合适的 BB,则输出 00

6 9 42
13

提示

p,q,rp,q,r 的所有位都是数字,并且 1p,q,r1061 \le p,q,r \le 10^6