PTA甲级—常用技巧与算法

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#define ll long long
#define inf 0x3f3f3f
using namespace std;
string s1, s2;
ll id, radix;
ll qpow(ll a, ll n){
    ll ans = 1;
    while(n){
        if(n&1) ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}
ll handle(string s, ll d){
    ll len = s.length(), num;
    ll sum = 0;
    for(int i = 0; i < len; i++){
        if(s[i]<='9') num = s[i]-'0';
        else num = s[i]-'a'+10;
        sum += num*qpow(d, len-1-i);
    }
    return sum;
}
int main(){
    cin >> s1 >> s2 >> id >> radix;
    if(id==2) swap(s1, s2);
    //cout << s1 << "    " << s2;
    ll tmp = handle(s1, radix);
    //二分+快速幂
    //char c=*max_element(str.begin(),str.end());
    int cnt = -1;
    for(int i = 0; s2[i]; i++){
        if(s2[i]<='9') cnt = max(cnt, s2[i]-'0');
        else cnt = max(cnt, s2[i]-'a'+10);
    }
    ll l = cnt, r = max(l, tmp)+1;
    while(r-l>1){
        ll mid = (l+r)/2;
        ll res = handle(s2, mid);
        if(res>=tmp||res<0) r = mid;
        else l = mid;
    }
    if(handle(s2, r)==tmp) printf("%lld
", r);
    else printf("Impossible
");
}