1010 Radix（25分）

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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//转化字符为数字
int toSet(char x){
    if (x>='0'&&x<='9'){
        return x-'0';
    }
    else if(x>='a'&&x<='z'){
        return x-'a'+10;
    }
}
//转化字符串为十进制数
ll toDecimal(string in,ll radix){
    ll result=0;
    for(int i=0;i<in.size();++i){
        result+=toSet(in[i])*pow(radix,in.size()-i-1);
    }
    return result;
}
//二分搜索
ll getRadix(ll head,ll tail,string in,ll d1){
    if (head<=tail){
        ll mid=(head+tail)/2;
        ll temp=toDecimal(in,mid);
        if (temp==d1){
            return mid;
        }
        else if(temp<d1&&temp>0){
            return getRadix(mid+1,tail,in,d1);
        }
        else if (temp>d1||temp<0){
            return getRadix(head,mid-1,in,d1);
        }
    }
    return -1;
}
int main(){
    int tag,radix;
    string n1,n2,temp;
    cin>>n1>>n2>>tag>>radix;
    if (tag==2){
        temp=n1;
        n1=n2;
        n2=temp;
    }
    ll d1=toDecimal(n1,radix);
    //定位最小进制
    int mmax=-1;
    for (int i=0;i<n2.size();++i){
        mmax=max(mmax,toSet(n2[i]));
    }
    ll result=getRadix(mmax+1,d1+1,n2,d1);
    if (result==-1){
        cout<<"Impossible";
    }
    else{
        cout<<result;
    }
}

我相信大多数人看到题面，按照自己的理解都会认为进制数在35以内，我也一样，看着永远ac不了的代码陷入了沉思，明明感觉是一道水题，就是过不了。

搜了题解，确实是长见识了，这竟然是一道二分搜索题，想了想也确实，就算超过35进制，按题目给的字符串也能表示，只能说是自己格局小了。

那么考虑到进制范围在2~N1+1内，在计算的过程中明显会溢出。难道这题还需要做一个大数相加？看了看题解的处理方法，他是将溢出直接作为不匹配条件进行下一次二分。我就在想，为什么N1不会溢出呢，如果N1也溢出了这种判断方法不就失效了吗？可能是出题人考虑到了这一点，并没有设置N1也溢出的测试点，不然只能乖乖地再去做大数相加。

tip：在二分判断时，不仅要在temp>d1时加一个是否溢出的判断，而且在temp<d1时也要加一个未溢出的判断，否则在溢出时永远满足temp<d1的条件；或者是把temp>d1的判断放到temp<d1前面去，也能起到一样的效果。