POJ 1331 - Multiply

http://poj.org/problem?id=1331

概要

数字 p, q, r が与えられる． これらをある B 進数とみて p * q == r が成り立つように B を定めたとき，その B を答える． ただし，そのような B が存在しないときは 0 を出力する．

制約

• 1 <= p, q, r <= 1000000
• 2 <= B <= 16

解法

B について全通り試すだけ．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int conv(int x, int base)
 6 {
 7   int r = 0;
 8   int e = 1;
 9   while (x > 0) {
10     r += (x%10) * e;
11     x /= 10;
12     e *= base;
13   }
14   return r;
15 }
16 
17 int main()
18 {
19   int T;
20   scanf("%d", &T);
21   while (T-- > 0) {
22     int p, q, r;
23     scanf("%d %d %d", &p, &q, &r);
24     int base = 0;
25     for (int x = p; x > 0; x /= 10) {
26       base = max(base, x%10);
27     }
28     for (int x = q; x > 0; x /= 10) {
29       base = max(base, x%10);
30     }
31     for (int x = r; x > 0; x /= 10) {
32       base = max(base, x%10);
33     }
34     for (++base; base <= 16; ++base) {
35       if (conv(p, base) * conv(q, base) == conv(r, base)) {
36         printf("%d\n", base);
37         goto NEXT;
38       }
39     }
40     puts("0");
41 NEXT:
42     ;
43   }
44   return 0;
45 }