202504281432 1010 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

Solve

这道题目要求找出一个合适的进制，使得两个数在不同进制下的值相等。具体来说：

• 给定两个数N₁和N₂，其中一个数的进制已知
• 需要找出另一个数的进制，使得它们的十进制值相等
• 如果有多个可能的进制，输出最小的一个
• 如果不存在这样的进制，输出”Impossible”

关键思路

1. 进制转换：将已知进制的数转换为十进制，作为目标值
2. 确定搜索范围：
   • 下限：未知进制数中出现的最大数位值+1
   • 上限：目标值（可以证明不需要搜索比目标值更大的进制）
3. 二分搜索：在确定的范围内搜索合适的进制
4. 处理边界情况：包括溢出、无解等情况

进制范围的确定

进制的下限很容易理解：必须大于数字中出现的最大数位值。例如，如果数字包含’b’（代表11），则进制至少为12。

进制的上限为什么是目标值？这可以通过数学推导得出：

• 设未知进制为r，长度为n的数字为a₁a₂…aₙ
• 其十进制值为：a₁×r^(n-1) + a₂×r^(n-2) + … + aₙ
• 当r足够大时，这个值主要由首项决定：a₁×r^(n-1)
• 要使这个值等于目标值t，必须有r^(n-1)≤t/a₁
• 由于n≥2且a₁≥1，可知r≤t

因此，我们只需要在[下限, 目标值]范围内搜索。

为什么使用二分搜索

由于随着进制的增加，数字的值单调递增，可以使用二分搜索提高效率。对于可能很大的目标值（最多10位数字），线性搜索效率太低。

这里使用优化后的整数二分模板。

为什么单独处理单字符情况

单字符情况下，解是直接可以计算的，不需要二分搜索：

• 对于单个字符c，在任何进制r(r > c的值)下，其值都是c本身
• 因此，如果有解，解一定是(数位值+1)

例如，字符’7’在任何r≥8的进制下值都是7，所以不需要搜索。

从数学角度看，单字符的情况有一个直观的解：

• 如果字符值等于目标值，则进制至少需要比字符值大1
• 所有大于等于(字符值+1)的进制都是可行的，我们取最小的

代码实现

#include<iostream>
#include<string>
#include<climits>
using namespace std;
 
// 获取字符对应的数值
int getDigitValue(char c) {
    if(isdigit(c)) return c - '0';
    if(islower(c)) return c - 'a' + 10;
    return -1; // 错误情况
}
 
// 从左到右将指定进制的数转换为十进制，提前检测溢出
long long to10Dex(const string& num, long long radix) {
    long long result = 0;
    for(char c : num) {
        int digit = getDigitValue(c);
        
        // 检查溢出
        if(result > (LLONG_MAX - digit) / radix)
            return LLONG_MAX; // 表示溢出
            
        result = result * radix + digit;
    }
    return result;
}
 
long long findSmallestRadix(string numA, long long targetValue) {
    if(numA.length() == 1) { // 单个数值在任何进制的值都不会变化，故直接特殊处理即可， 无需再进行二分查找
        int digit = getDigitValue(numA[0]);
        return digit == targetValue ? digit + 1 : -1;
    }
    
    char it = *max_element(numA.begin(), numA.end());
    long long low = (isdigit(it) ? it - '0': 10 + it - 'a'); // 进制最低是待比较数的最高位数+1
    long long high = max(low + 1, targetValue + 1); // 进制最高是另一个已确定数的数值 实际上应该设定为 LONG_MAX
 
    // 优化后的整数二分，要求 low,high 为要搜索范围的 [l-1, r+1]
    while(low != high - 1) {
        long long mid = low + (high - low) / 2;
        long long t = to10Dex(numA, mid);
 
        if(t > targetValue)
            high = mid;
        else
            low = mid;
    }
    
    long long value = to10Dex(numA, low);
    if(value == targetValue)
        return low;
    return -1;
}
 
int main() {
    string num[2];
    int tag;
    long long radix;
    cin >> num[0] >> num[1] >> tag >> radix;
    
    long long result = findSmallestRadix(num[2 - tag], to10Dex(num[tag - 1], radix));
    if(result != -1)
        cout << result << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}

这种方法有效地解决了进制转换问题，并能处理各种边界情况。时间复杂度为O(log(target)×length)，其中target是目标值，length是未知进制数的长度。