1010 Radix 甲级 xp_xht123

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

这应该是甲级最恶心的一道题了，以傲人的11%的正确率，屈居榜首

解题思路：

坑点一：需要使用long long 才能存的下最终的结果

有可能有这样一个数在36进制下的数，“ z ...... z ”，中间有很多的z，如果转换成某一进制下的数会非常的大，一定会超出int整型

坑点二：注意有字母，需要映射到10 ~ 35之间

坑点三： 由于坑点一的存在，所以答案有可能非常的大，不能使用普通的暴力的搜索，需要使用二分查找

 注意：答案不一定在36以内，只是给定需要转换的数的进制是在2 ~ 36之间的，但是答案一定小于转换出来的目标数。

因为一个数中的每一位数一定小于进制radix，二分的时候左端点不是0，而是每一位数中最大的那一位 + 1。

#include
#include
 
using namespace std;
 
typedef long long ll;
 
int get(char c)
{
    //将数字和字母映射到题目给定的范围
    if(c <= '9') return c - '0';
    return c - 'a' + 10;
}
 
ll calc(string n , ll r)
{
    ll res = 0;
    for(auto c : n)
    {
        //当给定的数是拥有十位数字的时候最多最多在36进制下是3e15左右的数，所以计算的结果超过1e16就不用再算了
        if((double)res * r + get(c) > 1e16) return 1e18;//过大的数用double
        res = res * r + get(c);//秦九韶算法
    }
    return res;
}
 
int main()
{
    string n1 , n2;
    cin >> n1 >> n2;
    int tag , radix;
    cin >> tag >> radix;
    
    if(tag == 2) swap(n1 , n2);//同一化为n1
    
    ll target = calc(n1 , radix);//将n1转换为radix进制下的目标数
    
    //使用二分查找
    ll l = 0 , r = target;
    
    //字符串中的每一位数一定小于进制radix
    //所以一定要加1
    for (auto c : n2) l = max(l, (ll)get(c) + 1);
    
    while(l < r)
    {
        ll mid = l + r >> 1;
        if(calc(n2 , mid) >= target) r = mid; // 说明进制过大
        else l = mid + 1;//进制过小
    }
    
    if(calc(n2 , l) != target) puts("Impossible");
    else cout << l << endl;
}