#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