Pat a - 1010 radical (thinking + two points)

Link

The question ： It means ,tag==1, be N1 by radix Binary number ;tag==2, be N2 by radix Binary number . How many base numbers does another number have to make N1==N2, No solution output "Impossible".

Ideas ： The basic idea is very simple , Directly enumerate the base of another number , Many details need to be paid attention to during the conversion of Radix . But if you enumerate directly, there will be a test point (1 branch ) Unable to get , It is not difficult to see the value of its base value, so we can query it by dichotomy , The lower limit of a binary is the maximum number of digits of another number maxx+1, Upper limit accession radix The decimal value of a decimal number +1.（ If you mistake Impossible Output into impossible only 18 branch ┭┮﹏┭┮）.

AC Code ：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f;
const int N = 1e5+10;

string a, b;
int x, y, tag, radix, maxx, ans=inf;
map<int, char> mp;

int get_int(char x){
    if(isdigit(x)) return x-'0';
    return x-'a'+10;
}

int to_int(string s, int k){
    int res = 0;
    res = get_int(s[0]);
    for(int i = 1; i < s.size(); i ++){
        res *= k;
        res += get_int(s[i]);
    }
    return res;
}

bool check(int k){
    int res = get_int(b[0]);
    for(int i = 1; i < b.size(); i ++){
        res *= k;
        res += get_int(b[i]);
        if(res<0||res>x) return 1;
    }

    if(res==x){
        ans = min(ans, k);
        return 1;
    }
    if(res<0||res>x) return 1;
    else return 0;
}

signed main()
{
    cin >> a >> b >> tag >> radix;
    if(tag==2) swap(a, b);
    x = to_int(a, radix);
    for(int i = 0; i < b.size(); i ++) maxx = max(maxx, get_int(b[i]));
    int l = maxx+1, r = x+1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    if(ans==inf) cout << "Impossible" << endl;
    else cout << ans << endl;

    return 0;
}