B1010 Radix(二分)

B1010 Radix (25分)

• Each case occupies a line which contains 4 positive integers:
  不用考虑为0的情况

• Here N1 and N2 each has no more than 10 digits.
  十位int会超，所以使用long long,但是long long在进行进制转换时还是会超，题中没有给出转换进制大小，所以要进行越界判断（第一处）

• A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35.
  基数的范围为2~35，2~∞？，和35没半毛钱关系

最小基数：A digit is less than its radix
所以是最大位数+1

最大基数：N2是一位数或两位数，一位数时，要满足上述最小基数的情况，两位数要满足不能超过N1的十进制数。

• For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true.
  搜索采用二分法，要在上界进行越界判断（第二处）
• If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
  这题来说二分查找结果唯一的吧(・∀・(・∀・(・∀・*)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX=10001;
const int INF=0x3f3f3f3f;
ll mp[MAX];
void init()
{
    for(char c='0';c<='9';c++)
    mp[c]=c-'0';
    for(char c='a';c<='z';c++)
    mp[c]=c-'a'+10;
}
ll getnum(string s,int radix)
{
    ll ans=0;
    for(int i=0;i<s.length();i++)
    {
        ans=ans*radix+mp[s[i]];
        if(ans<0)
            return -1;
    }
    return ans;
}
ll getlow(string s)
{
    ll maxnum=0;
    for(int i=0;i<s.length();i++)
    {
        if(maxnum<mp[s[i]])
            maxnum=mp[s[i]];
    }
    return maxnum+1;
}
ll binary(ll low,ll high,string s,ll number)//ll number 开始为int 测试点10
{
    while(low<=high)
    {
        ll mid=(low+high)/2;
        ll result=getnum(s,mid);
        if(result==number)
            return mid;
        else if(result>number||result==-1)
             high=mid-1;
        else if(result<number)
             low=mid+1;
    }
    return -1;
}
int main()
{
    string n1,n2;
    int tag,radix;
    cin>>n1>>n2;
    scanf("%d%d",&tag,&radix);
    init();
    if(tag==2)
    swap(n1,n2);
    ll num1=getnum(n1,radix);
    ll low=getlow(n2);//最小基数
    ll high=max(num1,low);//最大基数//测试点0
    ll ans=binary(low,high,n2,num1);
    if(ans!=-1)
        printf("%lld\n",ans);
    else
        printf("Impossible\n");
    return 0;
}