思路

知识点

• 秦九韶算法
  

LL cal(string str, LL r)
{
    LL res = 0;
    for (auto c : str)
    {
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);
    }
    return res;
}

注意判断一下，如果在算最高位时直接大于$36^{10}$ $(3*10^{15})$也就是最大进制，那准定是无解的，直接返回一个更大的比如1e18作为右边界就行。

我的错误历程

• 进制位r也的是long long 类型的

• 二分条件想错了：应该是找大于等于target的最小进制数 if(cal(s2, r)) >= target

• 关于二分的左右边界，还是得正常去找。左边界就是每位数中最大的数加一，右边界就是$36^{10}$ $(3*10^{15})$，如果在算最高位时直接大于$36^{10}$也就是最大进制，那准定是无解的，直接返回一个更大的比如1e18作为右边界就行。

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL ;

int get(char c)
{
    if (c <= '9') return c - '0';  // 刚开始写成了 9，应该写'9'
    else return c - 'a' + 10;
}

LL cal(string n, LL r)
{
    LL res = 0;
    for (auto c : n)
    {
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);
    }
    return res;
}

int main()
{
    string s1, s2;
    int tag, radix;

    cin >> s1 >> s2 >> tag >> radix;
    if (tag == 2) swap(s1, s2);

    // 转成十进制的target
    LL target = cal(s1, radix);



    LL l = 0, r = target + 1;  //  + 1
    for (auto c : s2) l = max(l, (LL)get(c) + 1);

    while(l < r)
    {
        LL mid = l + r >> 1;
        if (cal(s2, mid) >= target) r = mid;
        else l = mid + 1;
    }

    if (cal(s2, r) != target) puts("Impossible");
    else cout << r << endl;
    return 0;
}