PAT甲级1010.

目录

A1010

题目

样例

样例1

输入:

6 110 1 10

输出:

2

样例2

输入:

1 ab 1 2

输出:

Impossible

补充测试点

输入:

12 c 1 10

输出:

13

思路和坑点

　　此题的难点在于确定另外一个数进制的上下界，对于一个数字来说其进制的下届为单个位上的数字最大值+1，比如178900，该数的进制最小是10；其上界为该数的十进制数值（取不到），比如c9，该数的十进制129，如果其进制等于129，那么该数字应该表示成1，如果超过129，那么该数字无法用整数表示。
　　基于以上的原理，在该进制区间内筛选，由于范围比较大，因此使用long long数据类型，并且考虑溢出，使用二分法查找。
　　坑点
　　如果出现了该数的进制的下届超过了其十进制数值情况，上界应该下届和十进制数值中的最大值，如补充测试点所示。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int tonum(char c){                        //转化为数字 
    return isdigit(c)?c-'0':c-'a'+10;
}
ll todec(string s,ll r){                //转化为十进制数 
    ll sum=0L;
    for(int i=0;i<s.size();i++){
        sum=sum*r+tonum(s[i]);
    }
    return sum;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    string n1,n2;
    int tag;
    ll radix;
    cin>>n1>>n2>>tag>>radix;
    if(n1=="0"||n2=="0"){                    //特判 0的情况 
        if(n1==n2)    putchar('2');
        else puts("Impossible");
        return 0;
    }
    if(tag==2) swap(n1,n2);                    //统一第一个数为已知 
    
    ll a=todec(n1,radix);                    //计算n1的十进制 
    ll low=-1,high;                            //n2的radix的上下界                         
    for(int i=0;i<n2.size();i++){
        low=max((int)low,tonum(n2[i])+1);    //下界为每一位+1的最大值； 
    }
    high=a>low?a:low;                        //上界n1十进制数和者其进制下界的最大值
    ll ans=0L;
    while(low<=high){                        //二分查找最小的可能的radix 
        ll mid=(low+high)/2;
        if(todec(n2,mid)>a||todec(n2,mid)<0)    //如果进制太大，包括溢出成为负数的情况 
            high=mid-1;
        else if(todec(n2,mid)<a)                //如果进制太小 
            low=mid+1;
        else{
            ans=mid;break;
        }
    } 
    if(ans==0)    puts("Impossible");
    else    cout<<ans;     
    return 0;
}