[进制转换] 确定进制

确定进制

题目描述

6*9 = 42 对于十进制来说是错误的，但是对于13进制来说是正确的。因为, 6(13) * 9(13) = 42(13)，而 42(13) = 4 * 13 + 2 = 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 * 3 + 1 = 4(10) 和 121(3) = 1 * 3^2 + 2 * 3 + 1 = 16(10)。对于进制 10,有 11(10) * 11(10) = 121(10)。这种情况下，应该输出 3。如果没有合适的进制，则输出 0。

关于输入

输入有 T组测试样例。 T在第一行给出。每一组测试样例占一行，包含三个整数p, q, r。 p, q, r 的所有位都是数字，并且1<=p,q, r<=1,000,000

关于输出

对于每个测试样例输出一行。该行包含一个整数，即使得p * q = r成立的最小的B。如果没有合适的B，则输出 0。

例子输入

3
6 9 42
11 11 121
2 2 2
例子输出

13
3
0
解题分析

这个程序的主要目的是找到一个进制 $B$ （ $\leq B \leq 16$ ），使得给定的三个数字 $p$ , $q$ 和 $r$ 满足 $p * q = r$ 。如果存在多个这样的进制，程序会输出最小的一个；如果不存在，程序会输出 0。

程序的主要步骤如下：

读取输入：程序首先读取测试样例的数量 $T$ ，然后对于每个测试样例，读取三个数字 $p$ , $q$ 和 $r$ 。这三个数字都是字符串形式的十进制数。
遍历所有可能的进制：然后，程序遍历所有可能的进制 $B$ （从 2 到 16）。对于每个进制，程序会尝试将 $p$ , $q$ 和 $r$ 转换为这个进制的数。
转换数字：转换是通过 convert 函数实现的。这个函数接受一个字符串和一个进制，然后将字符串转换为这个进制的数。如果字符串中的任何一位数字大于等于进制，那么转换失败，函数返回 -1。否则，函数会计算出这个进制的数。
检查等式是否成立：如果 $p$ , $q$ 和 $r$ 都成功转换为了这个进制的数，那么程序会检查等式 $p * q = r$ 是否成立。这里需要注意的是，由于 $p$ 和 $q$ 的乘积可能超过整数的范围，所以需要使用 long long 类型来存储乘积。
输出结果：如果找到了一个合适的进制，程序会输出这个进制，并将 found 设置为 1，然后跳出循环。如果遍历完所有的进制都没有找到合适的进制，那么 found 仍然是 0，程序会输出 0。

这个程序的时间复杂度是 $O (T)$ ，其中 $T$ 是测试样例的数量。这是因为对于每个测试样例，程序需要遍历 15 个进制，并且每个进制的处理时间是常数。

代码实现

#include <stdio.h>
#include <string.h>

int convert(char *s, int base) {
    int res = 0;
    for (int i = 0; s[i]; i++) {
        int digit = s[i] - '0';
        if (digit >= base) return -1;
        res = res * base + digit;
    }
    return res;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        char p[10], q[10], r[10];
        scanf("%s %s %s", p, q, r);

        int found = 0;
        for (int base = 2; base <= 16; base++) {
            int vp = convert(p, base);
            int vq = convert(q, base);
            int vr = convert(r, base);

            if (vp == -1 || vq == -1 || vr == -1) continue;
            if ((long long)vp * vq == vr) {
                printf("%d\n", base);
                found = 1;
                break;
            }
        }

        if (!found) printf("0\n");
    }

    return 0;
}