思路

坑点：如果不注意到另一个进制可能很大，不止36，就可能不会考虑到二分。

使用二分算法注意：

1. 二分的左右边界
   左边界是未知进制的串中最大的数字+1
   右边界是十进制表示的已知进制数+1（此时在该进制下可用1位表示）
2. 题目要求：如果答案不唯一，则输出更小的进制数
   即求第一个使结果大于等于target的值

爆int注意

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int get(int c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'a' + 10;
}

LL calc(string n1, LL radix) { //秦九韶算法
    LL res = 0;
    for (auto c : n1) {
        if ((double)res * radix + get(c) > 1e16) return 1e18;//判断是否溢出
        res = res * radix + get(c);
    }
    return res;
}

int main() {
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;

    if (tag == 2) swap(n1, n2);
    LL target = calc(n1, radix);
    // cout << target << "\n";

    LL l = 0, r = target + 1;
    for (auto c : n2) l = max(l, (LL)get(c) + 1);
    while (l < r) { //第一个大于等于
        LL mid = l + r >> 1;
        if (calc(n2,mid) >= target) r = mid;
        else l = mid + 1;
    }
    // cout << l << ' ' << calc(n2, l) << "\n";
    if (calc(n2, l) != target) cout << "Impossible";
    else cout << l << "\n";

    return 0;
}