PAT 1010 Radix (25分) radix取值无限制，二分法提高效率

题目

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N2 , your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

题目解读

给出两个数N1,N2，给出其中一个数N1或N2的进制（输入数据中tag=1表示这这是给出的是N1的进制，tag=2表示给出的是N2的进制），为第二个数寻找合适的进制，使得 两者转换成10进制后的结果相等。输出找到的radix，如果不存在这样的进制，那就输出 ”Impossible“

N1和N2的长度最多为10，每个位置上的数字可以是 0-9 或 a-z，其中 a-z数字 10-35

注意：

每个数长度最多为10，每个位置大小都可以是0-35，那么int肯定是不够存的，比如这个数是zzzzzzzzzz，35 ^ 9 > 2 ^ 32，我们用 long long
并未从题中看出来radix的取值范围（不要自己觉得它最大是35），所以也要定义成 long long才保险。

思路分析

相信大家都能想到的是，先把给出的N1或N2（假设给出的进制是N1的进制）按照给出的进制转成十进制，然后从1开始测试每种进制，把N2转成十进制判断是否和N1相等，如不相等就增加进制，继续转换，比较。。。

问题是，如果这个进制存在还好说，我从1开始增加，总能找到那个进制；但是如果它不存在呢？增加到无穷大程序都跑不完。。。。

所以我们必须先确定radix的上限和下限。

（以第一个数进制给出，转换成十进制结果是N1，求N2的进制为例进行说明）

假如N2每个位置上的数字中最大的那个是 x ，那么N2的进制最小是 x + 1，比如你某个位置是0-9，最起码得是10进制吧。

那么它的进制的最大值是多少呢？？那么这个进制最大为 N1

为什么？？？

假如N2只有一位数，假设为x，那么你的进制可以是 比这个数本身大的任意数字，它所代表的值是 x * 进制 ⁰ = x，所以除非x和N1相等，否则你取啥进制都没办法。

假如N2有两位，那它最小也就是 '1 0'，代表的值是 1 * 进制 ¹ + 0 * 进制 ⁰ = 进制，所以N2的大小就等于进制的大小，如果你让N2的进制=N1时，N2都不能和N1相等，那么你把进制变得更大，N2转换后必然比N1更大。当N2有更多位时就更不用说了，肯定更不可能，每差一个位置，值就差的更多

所以N2的进制的取值范围是 【N2字符串中最大的那个字符代表的值+1，N1】

确定了进制的取值范围之后，我们可以用for循环进行遍历，但是复杂度比较高，这里我们选取二分法。

注意不要漏掉对溢出情况的判断，若N2在某进制下转换成十进制的结果大于N1，应该缩小右边界；但是，如果N2在某进制下转换成十进制的结果小于0，也要缩小右边界，小于0说明进制太大，它转换后long long都存不下了。

    while(low <= high) {

        long long mid = low + (high - low) / 2;

        long long temp = convert(numStr, mid);

        // temp < 0，代表得到的数字越界，temp > target都代表当前进制太大，需要调整上限

        if (temp < 0 || temp > target) high = mid - 1;

        // 当前进制正好

        else if (temp == target) return mid;

        // 当前进制太小

        else low = mid + 1;

    }

完整代码

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

/**

 * 给出两个数n1,n2，给出其中一个数n1及其进制radix，为第二个数寻找合适的进制使得 两者相等

 *

 * 首先，每个数长度最多为10，每个位置大小都可以是0-35，那么int肯定是不够存的，比如这个数是zzzzzzzzzz，35 ^ 9 > 2 ^ 32

 *

 * 加入这个数每个位置上的数字中最大的那个是 x ，那么这个数的【进制最小是 x + 1】，比如你要表示0-9，最起码得是10进制吧

 * 那么它的进制的最大值是多少呢？？其实这个是没有限制的，你可以是任意进制，所以我们用了long long来存

 *

 * 但在这个题中，必须要有一个合适的进制使得n2能转为n1，那么这个【进制最大为 n1】

 *

 * 为什么？？？

 *

 * 假如n2只有一位，那么你的进制只要比这个数字大，就可以任意取，随意，但除非你本身和n1相等,否则你取啥进制都没办法，

 * 因为最后一个位置是最低位，它代表的是 进制 ^ 0 = 1

 *

 * 假如n2有两位，那它最小也就是 10，1 * 进制 + 0 * 进制 ^ 0 = 进制，

 * 所以n2的大小就等于进制的大小，如果你让n2的进制=n1时，n2都不能和n1相等，那么你把进制变得更大，n2就更不可能转为n1

 * 当n2有更多位时就更不用说了，肯定更不可能，每差一个位置，值就差的更多

 *

 * 所以这个进制的取值范围是 【n2字符串中最大的那个字符代表的值+1，n1】，接着利用二分法

 *

 */

// 根据进制，把字符串转为实际数字

long long convert(string numStr, long long radix) {

    long long res = 0;

    int exp = 0; // 最低位指数为0

    // auto自动判断类型，rbegin()是最后一个字符，rend()是第一个字符

    for (auto it = numStr.rbegin(); it != numStr.rend(); ++it) {

        // '0'-'9'，注意这里要加*才能得到值

        if (isdigit(*it))

            res += (*it - '0') * pow(radix, exp++);

        // 'a'-'z'

        else

            res += (*it - 'a' + 10) * pow(radix, exp++);

    }

    // 返回结果

    return res;

}

// 找到合适的进制，使得numStr在这个进制下 == target

long long findRadix(string numStr, long long target) {

    // 找到字符串形式的n2中最大的那个字符，注意这里要加*才能得到值

    char maxChar = *max_element(numStr.begin(), numStr.end());

    // 转为数字加1，就是 进制的下限

    long long low = (isdigit(maxChar) ? maxChar - '0' : maxChar - 'a' + 10) + 1;

    // 进制的上限就是 n1

    long long high = max(low, target);

    // 二分法

    while(low <= high) {

        long long mid = low + (high - low) / 2;

        long long temp = convert(numStr, mid);

        // temp < 0，代表得到的数字越界，temp > target都代表当前进制太大，需要调整上限

        if (temp < 0 || temp > target) high = mid - 1;

        // 当前进制正好

        else if (temp == target) return mid;

        // 当前进制太小

        else low = mid + 1;

    }

    // 没找到合适的，返回-1

    return -1;

}

int main() {

    // 两个数，每个位置是0-9或a-z，a-z代表10-35，每个数最多长度为10，如果是35进制，最大为35 * 35 ^ 9, 大于2^32

    string n1, n2;

    // radix，基数（进制），tag为1代表这个基数针对于第一个数字，tag为2代表这个基数针对第2个数字

    int tag;

    long long radix;

    cin >> n1 >> n2 >> tag >> radix;

    long long res = tag == 1 ? findRadix(n2, convert(n1, radix)) : findRadix(n1, convert(n2, radix));

    // 不存在这样的进制

    if (res == -1)

        cout << "Impossible";

    else

        cout << res;

    return 0;

}

巴特西

PAT 1010 Radix (25分) radix取值无限制，二分法提高效率

题目

题目解读

思路分析

完整代码

最新文章

热门文章