本文共 1414 字，大约阅读时间需要 4 分钟。

【题意】

给定两个数N1，N2（均不超过10位），和一个tag（1或2）和radix（表示几进制），要求判断当数是一个radix进制数时，是否存在一种进制使得另一个数等于这个数成立。

【题解】

一开始我们很容易会以为进制数只可能在【2，36】，所以可能会枚举或者二分，但是只会有部分正确，为什么呢？

因为更大的进制数也有可能。虽然无法被全部表达，但是根据我们的N1或者N2和一个确定的更大的进制数是很容易得到他表达的值的。然后我们考虑选择二分和二分的范围，最小值肯定会>=2，但是同时也要大于给定的进制数中的最大值，比如'1a'，那么进制数最小肯定是11；最大值是多少呢？题目说给定的数据不会超过十位，所以我们把最大值定为1e11即可。题目要求有多种答案时，输出最小的一个，所以我们在二分得到计算结果等于所表示的数时，还要缩小右端点r，继续判断。

坑点：计算时可能会炸longlong，为了避免溢出带来的干扰，我们在二分得到计算结果为负数时，也选择缩小取值范围。

【代码】

#include 
   
    using namespace std;#define ll long longll ans=-1;ll cul(string s,ll x){    ll ret=0;    for(int i=0;s[i];i++)        ret=ret*x+((s[i]>='0'&&s[i]<='9')?s[i]-'0':s[i]-'a'+10);    return ret;}void solve(string s,ll a,ll mi){    ll l=mi,r=(ll)1e12;    while(l<=r){        ll mid=(l+r)/2;        ll x=cul(s,mid);        if(x==a){            ans=mid; r=mid-1;        }        else if(x>a||x<0) r=mid-1;        else l=mid+1;    }}ll getmi(string a){    ll aa=2;    for(int i=0;a[i];i++)        if(a[i]>='0'&&a[i]<='9') aa=max(aa,(ll)a[i]-'0'+1);        else aa=max(aa,(ll)a[i]-'a'+11);    return aa;}int main(){    string a,b; ll tag,rad;    cin>>a>>b>>tag>>rad;    int aa=getmi(a),bb=getmi(b);    ll x;    int f=1;    if(tag==1){        if(aa>rad) f=0;        x=cul(a,rad);        solve(b,x,bb);    }    else{        if(bb>rad) f=0;        x=cul(b,rad);        solve(a,x,aa);    }    if(f&&ans!=-1) printf("%lld\n",ans);    else printf("Impossible\n");    return 0;}
   

转载地址：http://qhfen.baihongyu.com/