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

Scroll Down

题目

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 N​1​​ and N​2​​ , 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

N1N2的长度最多为10,每个位置上的数字可以是 0-9a-z,其中 a-z数字 10-35

注意:

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

思路分析

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

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

所以我们必须先确定radix的上限和下限
(以第一个数进制给出,转换成十进制结果是N1,求N2的进制为例进行说明)

  • 假如N2每个位置上的数字中最大的那个是 x ,那么N2的进制最小是 x + 1,比如你某个位置是0-9,最起码得是10进制吧。
  • 那么它的进制的最大值是多少呢??那么这个进制最大为 N1

    为什么???

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

    假如N2有两位,那它最小也就是 '1 0',代表的值是 1 * 进制 1 + 0 * 进制 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; 
}