PTA甲级——1010

1010 Radix

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 N1 and N2, 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:

1
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:

1
6 110 1 10

Sample Output 1:

1
2

Sample Input 2:

1
1 ab 1 2

Sample Output 2:

1
Impossible

思路

​ 大致题意：给两个数，N1,N2,后面的tag=1的时候，那么radix为N1的进制，反之则为N2的进制位。题目需要我们判断是否存在一种进制可以使得另一个数转换为统一进制之后二者相同。

​ 思路：这道题目实际上就是一个进制转换 + 二分查找的一种思路就ok了的，首先将已知进制的数转换为十进制，然后我们再判断一下另一个数的最小进制，也就是另一个数中的最大值 + 1即为最小进制，但是我们需要注意一个问题，虽然题目给我们的要求是最大可以到的表示的为'z'也就是35,但是并没有说37、38等进制不可以呀，所以我们需要让进制的最大值设置为这个数。

​ 再往下走就是我们需要进一步确定真正的进制为多少，而且我们可以很容易地知道这个进制升高和降低肯定会对这个数所表示的十进制数有一种单调性的影响，因此我们可以想到使用二分的方法来寻找这个进制数，如果出现了找不到的情况就直接返回-1,这个时候输出impossible,反之输出进制数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cmath>

using namespace std;
typedef long long LL;
int n;

// 字符转数字
LL toInt(char c)
{
    if (isdigit(c)) return c - '0';
    return c - 'a' + 10;
}

// 转换为二进制
LL transform(string s, LL k) {
    LL res = 0;
    for (int i = 0; i < s.length(); i++) {
        int num, kk = s.length() - i - 1;
        if (s[kk] >= '0' && s[kk] <= '9') num = s[kk] - '0';
        else num = s[kk] - 'a' + 10;
        res += num * pow(k, i);
    }

    return res;
}

// 重写
LL max(LL a, LL b)
{
    return a > b ? a : b;
}

// 二分
LL binarySearch(LL low, LL high, string n,LL a)
{
    while (low <= high) {
        LL mid = (low + high) / 2;
        LL value = transform(n, mid);
        if (value < 0) high = mid - 1;
        else if (value < a) low = mid + 1;
        else if (value == a) return mid;
        else high = mid - 1;
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string N1, N2;
    LL tag, radix;
    cin >> N1 >> N2 >> tag >> radix;
    if (tag == 2) {
        swap(N1, N2);
    }
    
    LL a = transform(N1, radix);
    
    // 求最大进制位
    LL maxDigit = 0;
    for (int i = 0; i < N2.length(); i++) {
        if (toInt(N2[i]) > maxDigit)
        maxDigit = toInt(N2[i]);
    }
    LL low = maxDigit + 1;
    LL high = max(low, a) + 1;
    LL r = binarySearch(low, high, N2, a);
    if (r == -1) cout << "Impossible";
    else cout << r;
    return 0;
}