PAT1010

这个题可太秀了，本来以为是一道水题，结果死活19分。然后网上查了一下代码，结果需要用到二分（黑人问号？？？干嘛要二分），然后看了一下别人代码里的进制搜索的右边界，竟然是给的数的十进制+1，突然发现自己想当然的把有边界写到了36。然后把36改成了10001，结果真对了23分，知道方向错了后，果断二分。结果一直卡在24分样例10上，我看人家说这个是溢出了，我想我做了溢出判断啊，然后疯狂操作，还是不行。突然看了一下代码，我的mid是用int类型定义的（全code唯一一个int），然后我想也不应该啊，进制数的mid咋可能爆炸呢，除非它给的样例的已知进制的那个数的10进制数爆int才可能啊。但是本着全code一致原则，改了交了，结果对了，这个数据真是绝了。

https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

#include<cstdio>
#include<cstring>

typedef long long ll;

ll tag,radix;

ll ans = -1;

char N1[15],N2[15];

ll numTrans(char c)
{
    if(c >= '0' && c <= '9') return c - '0';
    if(c >= 'a' && c <= 'z') return c - 'a' + 10;
}

ll trans(char* str,ll r)
{
   ll sum = 0;
   ll flag = 1;
   for(ll i = strlen(str)-1;i >= 0;i--,flag*=r)
   {
        ll temp = flag * numTrans(str[i]);
        sum += temp;
        if(temp < 0 || sum <0 || flag < 0) return -1;
   }
   return sum;
}

ll findMax(char *str)
{
    ll maxn = 0;
    for(ll i = 0;i < strlen(str);i++)
    {
        if(numTrans(str[i]) > maxn)
            maxn = numTrans(str[i]);
    }
    return maxn;
}

void binSearch() 
{
    ll sum = 0;
    sum = trans(N1,radix);
    ll rad = findMax(N2);
    ll down = rad +1;
    ll top = sum +1;
    while(top >= down)
    {
        ll mid = (top+down)/2;
        ll temp = trans(N2,mid);
        if(temp >= sum || temp == -1)
        {
            top = mid - 1;
            if(temp == sum)
                ans = mid;
        }
        else
            down = mid + 1;

    }
}

int main()
{

    scanf("%s%s%lld%lld",N1,N2,&tag,&radix);

    if(tag == 2)
    {
        char tt[15];
        strcpy(tt,N1);
        strcpy(N1,N2);
        strcpy(N2,tt);
    }

    binSearch();
    if(ans != -1) printf("%lld\n",ans);
    else
        printf("Impossible\n");

    return 0;
}