*A1010 Radix

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

难点：

1. 取出当前位
2. 确定二分的上下界限
3. t<0怎么来的？

2.25update: t<0的时候表示溢出

#include<algorithm>
#include<string>
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
using namespace std;
long long convert(string n1, long long radix){
    //cout<<"radix = "<<radix<<endl;
    long long ans = 0, temp = 0;
    int index = 0;
    for(auto it = n1.begin();it!=n1.end();it++){
        temp = isdigit(*it) ? *it - '0': *it - 'a' + 10;//取出当前位
        //cout<<"ans = "<<ans<<"radix = "<<radix<<"temp = "<<temp<<endl;
        ans  = ans * radix + temp;    
    }
    return ans;
}
long long find_radix(string n, long long num) {
    char it = *max_element(n.begin(), n.end());//n中最大的元素
    long long low = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;//进制至少是这么多
    long long high = max(num, low);//最大是num这么多和low的界限
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long t = convert(n, mid);
        if (t < 0 || t > num) high = mid - 1;//小于0是怎么来的？
        else if (t == num) return mid;
        else low = mid + 1;
    }
    return -1;
}
int main(){
    string n1, n2;
    long long tag, radix;
    cin>>n1>>n2;
    scanf("%lld%lld", &tag, &radix);
    //先转化
    if(tag == 2) swap(n1, n2);
    long long t = convert(n1,radix);
    long long result = find_radix(n2, t);
    if (result != -1) {
        printf("%lld", result);
    } else {
        printf("Impossible");
    }   
    return 0;
}