1010 Radix

 
N1 N2 tag radix

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

题目大意

给我们N1，N2，tag，radix四个数，tag为1表示N1为radix进制，反之N2为radix进制

让我们求另外一个数为几进制时，可以让 N1=N2成立

思路

首先确保N1与N2其中一个是固定已知的进制数(方便后续判断)

即tag=1时候保持不变,tag为2时交换N1与N2

num1 = N1 为 radix 进制时转换而来的10进制

接着二分查找符合要求的进制

OP(num,op)，将op进制的N2转换为十进制的key，注意这里可能会溢出，所有只要溢出(key为负数)，就算N2在op进制下比num1大

注意如果不唯一输出最小情况,如果当前op进制下的N2已经等于key了,我们仍需继续往下判断

C/C++ 

#include
using namespace std;
typedef long long LL;
LL OP(const string& num,LL op); // 将num转换为op进制
int main()
{
    string N,N1,N2;
    LL op1,op2;
    cin >> N1 >> N2 >> op1 >> op2;
    if(op1==2) N = N2, N2 = N1 , N1 = N;
    LL num1 = OP(N1,op2);
 
    char flag  = *max_element(N2.begin(),N2.end()); // 找到N2中最大的那个字符
    LL head = isdigit(flag) ? flag - 47 : flag - 86;
    LL tail = max(num1,head),result=-1;
    while (head<=tail){
        LL avg = (head+tail)/2;
        LL key = OP(N2,avg);
        if(key==num1){
            result = avg;
            tail = avg-1;
        }else if(key<=0 || key>num1) tail = avg-1;
        else head = avg+1;
    }
    
    if(result==-1) cout << "Impossible" << endl;
    else cout << result << endl;
    return 0;
}
LL OP(const string& num,LL op)
{
    LL result = 0;
    for(char ch : num){
        int key = ch - 48;
        if(ch>='a' && ch<='z') key = 10 + ch - 97;
        result = result * op + key;
    }
    return result;
}