题目描述
6 ×9=42 对于十进制来说是错误的,但是对于 13 进制来说是正确的。即 6(13) ×9(13)=42(13),而 42(13)=4 ×131+2 ×130=54(10)。
你的任务是写一段程序读入三个整数 p,q 和 r,然后确定一个进制 B(2≤B≤16) 使得 p ×q=r。如果 B 有很多选择,则输出最小的一个。
例如:p=11,q=11,r=121,则有 11(3) ×11(3)=121(3),因为 11(3)=1 ×31+1 ×30=4(10) 和 $121_{(3)}=1\ \times 3^2+2\ \times 3^1+1\ \times 3^0=16_{(10)}$。对于进制 10, 有 11(10) ×11(10)=121(10)。这种情况下,应该输出 3。如果没有合适的进制,则输出 0。
输入格式
一行,包含三个整数 p,q,r,相邻两个整数之间用单个空格隔开。
输出格式
一个整数:即使得 p×q=r 成立的最小的 B。如果没有合适的 B,则输出 0。
6 9 42
13
提示
p,q,r 的所有位都是数字,并且 1≤p,q,r≤106。