Radix

题目链接

Radix

题目思路

不妨设 N₁ 是确定进制的数，讲该数转换成十进制数。我们要求 N₂ 的进制。由于位数低的时候进制数可能会很大我们分情况讨论，设进制数为x。

N₂.size =  = 1 的时候

直接判断 N₂ 是不是等于 N₁

N₂.size =  = 2 的时候

设N₂ = a₀a₁ ,我们有方程 a₀x + a₁ = N₁ ，如果x有整数解且整数解满足N₂的进制要求，则输出x，否则无解。

N₂.size =  = 3 的时候

设 N₂ = a₀a₁a₂ ,我们有方程 a₀x² + a₁x + a₂ = N₁ 解方程即可

N₂.size > 3 的时候

直接遍历进制即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a0,a1,tag,radix,cnt1=0,d=0;
    string n1,n2;
    bool flag=0;
    cin>>n1>>n2>>tag>>radix;
    if(tag==2)swap(n1,n2);
    for(int i=n1.length()-1;i>=0;i--){
        if(n1[i]>='0'&&n1[i]<='9')cnt1+=(n1[i]-'0')*pow(radix,n1.length()-i-1);
        if(n1[i]>='a'&&n1[i]<='z')cnt1+=(n1[i]-'a'+10)*pow(radix,n1.length()-i-1);
    }
    for(auto i:n2){
        if(i>='0'&&i<='9'){if(i-'0'+1>d)d=i-'0'+1;}
        if(i>='a'&&i<='z'){if(i-'a'+11>d)d=i-'a'+11;}
    }
    if(n2.length()==2){
        if(n2[0]>='0'&&n2[0]<='9')a0=n2[0]-'0';
        else a0=n2[0]-'a'+10;
        if(n2[1]>='0'&&n2[1]<='9')a1=n2[1]-'0';
        else a1=n2[1]-'a'+10;
        if((cnt1-a1)%a0==0&&(cnt1-a1)/a0>=d)cout<<(cnt1-a1)/a0;
        else cout<<"Impossible";
        return 0;
    }
    for(int i=d;1;i++){
        int cnt2=0;
        for(int j=n2.length()-1;j>=0;j--){
            if(n2[j]>='0'&&n2[j]<='9')cnt2+=(n2[j]-'0')*pow(i,n2.length()-j-1);
            if(n2[j]>='a'&&n2[j]<='z')cnt2+=(n2[j]-'a'+10)*pow(i,n2.length()-j-1);
        }
        if(n2.length()==1){
            if(cnt2!=cnt1){
                cout<<"Impossible";
                break;
            }
        }
        if(cnt1==cnt2){
            cout<<i;
            break;
        }
        if(cnt2>cnt1){
            cout<<"Impossible";
            break;
        }
    }
    return 0;
}