POJ1331 UVALive2526 Multiply【暴力＋進制】

Multiply

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 5943	Accepted: 3084

Description

6*9 = 42" is not true for base 10, but is true for base 13. That is, 6(13) * 9(13) = 42(13) because 42(13) = 4 * 131 + 2 * 130 = 54(10).  

You are to write a program which inputs three integers p, q, and r and determines the base B (2<=B<=16) for which p * q = r. If there are many candidates for B, output the smallest one. For example, let p = 11, q = 11, and r = 121. Then we have 11(3) * 11(3) = 121(3) because 11(3) = 1 * 31 + 1 * 30 = 4(10) and 121(3) = 1 * 32 + 2 * 31 + 1 * 30 = 16(10). For another base such as 10, we also have 11(10) * 11(10) = 121(10). In this case, your program should output 3 which is the smallest base. If there is no candidate for B, output 0.  

Input

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of three integers p, q, and r in a line. All digits of p, q, and r are numeric digits and 1<=p,q, r<=1,000,000.

Output

Print exactly one line for each test case. The line should contain one integer which is the smallest base for which p * q = r. If there is no such base, your program should output 0.

Sample Input

3
6 9 42
11 11 121
2 2 2
      

Sample Output

13
3
0

      

Source

Taejon 2002

Regionals 2002 >> Asia - Taejon

問題連結：POJ1331 UVALive2526 Multiply

問題簡述：（略）

問題分析：

　　這是一個簡單的進制轉換問題。

　　輸入的資料都是有數字（0-9）組成的。

　　由于如果有兩個答案的話則輸出小的值，是以需要從小到大試探進制。

　　開始時，先将資料按照10進制讀入，然後再轉換為指定的進制。

程式說明：

　　編寫了共用的函數convert()用于轉換資料。　

題記：

　　将共用功能用封裝到函數中是一種好的做法。

參考連結：（略）

AC的C語言程式如下：

/* POJ1331 UVALive2526 Multiply */

#include <stdio.h>

#define BASE10 10
#define START 2
#define END 16

int convert(int val, int base)
{
    int ans, weight, r;

    ans = 0;
    weight = 1;
    while(val) {
        r = val % BASE10;
        val /= BASE10;

        if(r >= base)
            return -1;

        ans += weight * r;

        weight *= base;
    }

    return ans;
}

int main(void)
{
    int t, p, q, r, i;
    int p2, q2, r2;

    scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &p, &q, &r);

        for(i=START; i<=END; i++) {
            p2 = convert(p, i);
            if(p2 < 0)
                continue;

            q2 = convert(q, i);
            if(q2 < 0)
                continue;

            r2 = convert(r, i);
            if(r2 < 0)
                continue;

            if(p2 * q2 == r2)
                break;
        }

        printf("%d\n", i <= END ? i : 0);
    }

    return 0;
}