PAT_1010 Radix (二分，溢出处理)

题目链接

这道题其实思路并不难，将已知进制的数字转化为十进制，然后枚举未知数字的进制也转化为十进制来比较，上下界写对且顺序查找的话pta上只有测试点7会TLE,也能最高拿24分（但是上下界写错就只能22分了，超时-1，上下界的坑各-1），但是在牛客上很多测试点会超时，鉴于进制越大对应转化得到的十进制数字也会很大，即是递增的，因此可以用二分查找。

但是此题还有很多坑点：

1.首先转化为十进制后有些数据也是超long long的表示范围的，有两种解决方式：

① 采用unsigned long long，但是要小心的是无符号数0一旦减1就会得到很大的数，因此使用typedef unsigned long long LLU之后，一定要小心在for(LLU i=xx; i≥0 ; i–) 就会导致死循环（-1强转为无符号数还是≥0），因此所有变量并不一定都能定义为LLU；

② 改变二分的条件，既然超出long long正数最大值即溢出时数值会变为负值，因此t<0也是进制过大的表现，此时也要修改right右边界，同时要注意if elseif 几个的顺序，毕竟t<0时会满足t<tmp，但是不能修改left；

if(t<0 || t>tmp) {//注意几个判断句的顺序
    right=mid-1;
}else if(t==tmp){
    flag=true;
    break;
}else left=mid+1;
           

2.二分查找的上下界的确定

一开始还分了两个原始数字谁大谁小来讨论确定上下界，事实证明没必要，少搜那么几个数字对时间复杂度几乎没影响，但是却增加思考量；

进制下界应该是未确定进制数字的最大位＋1，比如‘456’进制不确定，但是进制下界至少为7，这一点一开始忽略了，想当然的从2开始搜，导致第0个和第19个测试点都过不去；（测试点0对应的是上限值坑，测试点19对应的是下限值坑）

进制的上界有可能是已经确定进制的数字的十进制数值，以此为进制，再不济另一个数为1的话，也能与之相等，但是如果是6 6 1 10这种例子，即进制比原数据大的情况，显然此例结果为7，但是依据前者的上界right会为6，二分查找会失败，因此进制的上界还可能是刚提到的进制下界，因此总的进制上界为这两种可能的max。(也就是要考虑到已知进制数字转为10进制的数字本身都小于前者进制下界的情况) 对于第二种可能进制上界不必选为此时的radix（如这里的10），因为此时已知数字的10进制表示已经比left进制小了，因此只需要查找一下这个left进制下能不能相等就够了（也就是看原始俩数字本身是不是一样就行了，但是不能直接通过比较N1和N2相等就笼统输出radix，否则对于6 6 1 10，将会输出10，但是答案应为7）。

参考大佬的写法得到进制下界

char it = *max_element(N2, N2+strlen(N2));
left = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
           

·

·

·

·

·

完整AC代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long LLU;
LLU getNum(char N[], LL radix){//返回转化为10进制的数值
    LLU res=0;
    LLU base=1;
    LL len=strlen(N);
    for(LL i= len - 1; i >= 0; i--){//i不能定义为LLU，否则会死循环
        LL y;
        if(N[i]>='0' && N[i]<='9'){
            y=N[i]-'0';
        }else{
            y=N[i]-'a'+10;
        }
        res+=y*base;
        base=base*radix;
    }
    return res;
}

int main() {
    LL tag,radix;
    char N1[15],N2[15],n1[15],n2[15];
    scanf("%s %s %lld %lld",n1,n2,&tag,&radix);
    LLU tmp=0;//都转化为N1为已知进制数字，N2为未知
    if(tag==1){
        strcpy(N1,n1);
        strcpy(N2,n2);
        tmp=getNum(n1,radix);
    }else{
        strcpy(N1,n2);
        strcpy(N2,n1);
        tmp=getNum(n2,radix);
    }
    LLU left,right,mid;//进行二分查找,右边界就是以十进制的自己，最不济就是N2就是1 (左右边界找错了)
    bool flag=false;
    char it = *max_element(N2, N2+strlen(N2));
    left = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
    right = max(left,tmp);
    while(left<=right){
        mid=left+(right-left)/2;
        LLU t=getNum(N2,mid);
        /*if(t<0 || t>tmp) {//不定义为LLU的话就要这样写了
            right=mid-1;
        }else if(t==tmp){
            flag=true;
            break;
        }else left=mid+1;*/
        if(t<tmp){
            left=mid+1;
        }else if(t>tmp){
            right=mid-1;
        }else{
            flag=true;
            break;
        }
    }
    if(flag) cout << mid;
    else cout << "Impossible";

    return 0;
}