思路

这道题虽然说是进制转换，但也是一道练习二分的好题目
主要是要确定下来二分的左右边界

ULL l = get(it) + 1, r = target + 1;

1. 为什么用ULL？
   因为可能会爆long long就会变成复数，解决方法就是在check的时候判断一下是后 < 0溢出了
   另外一种方法就是用无符号数，这样即使溢出了也是一个1e18数量级的大数，而我们的答案最多是10个z
   也就是 3 * 10^15 这么大, 转换完依旧满足 > target这个条件
2. max_element
   在string中便利返回了一个最大值的迭代器
3. 左边界 l 是因为最小的进制数至少是这个字符串中最大数+1
4. 右边界 r 是因为最大的进制数
5. 这道题目无法通过扩大右边界，然后通过最后时候二分到越界边界来判断。因为target不准，会溢出

$(10)_{12}$

代码

#include <bits/stdc++.h>
using namespace std;

#define Debug(x) cout << "[" << #x << ": " << (x) << "]" << endl
#define get(x) (isdigit(x) ? x - '0' : x - 'a' + 10)
typedef unsigned long long ULL;
string n1, n2;
int tag, radix;

// 将r进制的n转换为10进制
ULL convert(string n, int r) {
    ULL sum = 0;
    for (auto c: n){
        ULL tmp = get(c);
        sum = sum * r + tmp;
    }
    return sum;
}

ULL find(string n, ULL target) {
    auto it = *max_element(n.begin(), n.end());
    ULL l = get(it) + 1, r = target + 1;
    while (l < r){
        ULL mid = l + r >> 1;
        if (convert(n, mid) >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    cin >> n1 >> n2 >> tag >> radix;
    if(tag == 2) swap(n1, n2);
    ULL target = convert(n1, radix);
    ULL res = find(n2, target);
    if(convert(n2, res) != target) puts("Impossible");
    else cout << res << endl;
}