PAT A1010 Radix(25)[进制，进制]

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers $N_1$ and $N_2$, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. 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. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

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.

Sample Input 1:

6 110 1 10    

Sample Output 1:

2   

Sample Input 2:

1 ab 1 2    

Sample Output 2:

Impossible

题意

若 tag = 1 $N_1$的进制为radix，否则若 tag = 2 $N_2$的进制为radix，求未被赋予进制的数的进制使得两个数在不同的进制下值相等

思路1

1. 统一将$N_1$的 radix 进制数转换为十进制数 target (若不满足则交换)
2. if((double)res * r + get(c) > 1e16) return 1e18; 退出否咋会爆掉
3. 字符转进制，0-9 a-z 在 36 进制下的映射
4. 二分查找满足条件的进制使得 k 进制数$N_{2}$ 的十进制为 target ，结果即为 k
5. 二分查找之前确定范围，最大可能进制为 36-target 最小可能进制为出现字符表示的进制数的最大值 + 1

代码1

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

// 字符转进制 
int get(char c)
{
    if(c <= '9') return c - '0';  // 0-9
    return c - 'a' + 10;          // a-z    
} 

// 计算正整数 s 在 r 进制下的十进制数 
LL cal(string s, LL r)
{
    LL res = 0;
    for(const auto &c : s)
    {
        if((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);
    }
    return res;
}

int main()
{
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;

    if(tag == 2)  swap(n1, n2);  // radix 指的是 n1
    LL target = cal(n1, radix); // 对应的十进制数


    // 二分查找
    LL l = 0, r = max(target, 36ll); // 最大可能进制
    for(auto c: n2) l = max(l, (LL)get(c) + 1);  // 最小可能进制

    while(l < r)
    {
        LL mid = l + r >> 1;
        if(cal(n2, mid) >= target)
            r = mid;
        else 
            l = mid + 1;    
    }
    if(target != cal(n2, l)) puts("Impossible");
    else printf("%lld\n", l);
    return 0;
 }