这种进制的题目之前做的还是比较少
这个题目暴力事实上思路还是很简单的 就是为了不TLE需要加许多优化

基本思路

题意还是比较明确的 给定一个任意进制的数a 并给定其进制 再给一个数b判断这个数在什么进制的情况下会与a相等
最直观的想法就是把a转换为10进制数(因为任意进制数转换为十进制数都可以通过按权展开的原则比较容易)
然后依次枚举b的可能进制并将其转换为十进数并判断a,b是否相等然后输出答案

暴力做法

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;

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

LL calc(string n,LL r)
{
    LL res=0;

    int k=0;

    for(int i=n.size()-1;i>=0;i--)
    {
        res+=get(n[i])*pow(r,k++);
    }

    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); //求出n1所对应的十进制数

    LL l=0;

    for(auto c:n2)
        l=max(l,get(c)+1ll);

    bool flag=false;
    int ans=0; 
    for(int i=l;i<=36;i++)
        if(calc(n2,i)==target)
        {
            flag=true;
            ans=i;
            break;
        }

    if(flag)
        cout<<ans;
    else
        puts("Impossible");

    return 0;
}

在这里吐槽一句这个数据有那么一些弱
这个做法过了整整20个 只是卡在了最后一个
不知道PAT是怎么给分的…

关于如何优化

通过上述暴力算法我们可以看到有两个地方是可以优化加速的
1.calc函数 即对于进制数转换为十进制过程中运算
由于是按权展开所以这个过程是个多项式加法，即符合秦九韶算法

vector<int>num; //存储多项式 按从高到低排序
for(auto x:num)
{
    res=res*r+x;    
}

2.就是对于进制的枚举可以使用二分进行枚举
这是由于十进制是按权展开来计算的 所以显然权值越大 则所得到的target值越大
这是一个单调的过程 所以可用二分进行优化

优化后的代码

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

typedef long long LL;

//get函数用于返回字母对应数值
int get(char c)
{
    if(c<='9')
        return c-'0';
    return c-'a'+10;
}

//秦九韶算法快速计算多项式提高计算速度
LL calc(string n,LL r)
{
    LL res=0;
    for(auto c:n)
    {
        if((double)res*r+get(c)>1e16)   //由于转换后的值换很大d超过long long
            return 1e18;                //而所以用double进行
        else
            res=res*r+get(c);
    }

    return res;
}


int main()
{
    string n1,n2;   //正整数N1，N2

    cin>>n1>>n2;

    int tag,radix;  //tag表示第几个数的进制 radix为进制

    cin>>tag>>radix;

    if(tag==2)
        swap(n1,n2);    //方便接下来的操作默认已知第一个数的进制

    LL target = calc(n1,radix);     //target为n1转换为十进制数后的目标数

    LL l=0, r = max(target,36ll);   //二分进制 用于加速

    for(auto c:n2)
        l=max(l,(LL)get(c)+1);  //进制最小值一定是的单个字母的值+1

    while(l<r)  //进行二分枚举操作 寻找到最接近答案的进制
    {
        LL mid = l+r>>1;
        if(calc(n2,mid)>=target) r=mid;
        else
            l=mid+1;
    }

    if(calc(n2,r)!=target)      //如果找到了最接近的进制数后转换出的十进制值仍然不等于target则输出impossible
        puts("Impossible");
    else
        cout<<r<<endl;




    return 0;
}