PAT 甲级 A1010 Radix (25 分)

题目传送门

这个题用二分做，我自己写的二分呢太菜了，只能拿到19分,不放出来丢人了。后面看了yxc的代码，美妙绝伦哈。
慢慢来拜读一下。

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int get(char c){
    if (c<='9') return c-'0';
    return c-'a'+10;
}
ll convert(string a,ll radix){
    ll res=0;
    for(auto c:a){
        if ((double)res*radix+get(c)>1e16) return 1e18;
        res = res * radix+get(c);
    }
    return res;
}

int main(){
    string N1,N2;
    int tag,radix;
    cin>>N1>>N2>>tag>>radix;

    if (tag == 2) swap(N1,N2);
    ll res = convert(N1,radix);

    ll low=0,hight=max(res,36ll);
    for(auto c:N2) low = max(low,(ll)get(c)+1);
    while (low<hight){
        ll mid = low+hight>>1;
        cout<<low<<" "<<hight<<" "<<mid<<endl;
        if (convert(N2,mid)>=res) hight = mid;
        else low = mid +1;
    }
    if (convert(N2,hight)!=res)cout<<"Impossible";
    else cout<<hight<<endl;
}

有几处美妙绝伦的点：

1. get函数直接把1~9 a~z都转化为int
2. convert用增强型for循环，配合get函数让代码短起来了。不然的话又要写一个分支出来。以及判断爆long long的情况。
3. 写的最好的是这个二分法了吧。。这个二分法会自动找出来最小的满足条件的进制并返回，而不是最传统的二分板子，会直接二分找到中间那个。