PAT甲级真题1100 – Radix

Posted on In Views:

题目链接：PAT - Advanced Level - 1100

给定一个 \(r\) 进制的数字 \(x\)，和一个未知进制的数字 \(y\)，求是否存在一个 \(t\)，使得 \(y\) 在 \(t\) 进制下等于 \(r\) 进制的 \(x\)。

题解：二分答案，渐进时间复杂度 \(O( \max \{ |s_x|, |s_y| \} \log n)\)。

坑点：原本我以为 \(t_{\max} = 36\)，其实可能更大。

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
w = {}
def dictInit():
    for i in range(0, 10):
        w[str(i)] = i
    for i in range(10, 36):
        w[chr(ord('a') + i - 10)] = i
    return w

def cal(ori, h):
    r = 0
    for c in ori:
        r = r * h + w[c]
    return r

def binarySearch(l, r, ori, tar):
    while l < r:
        mid = (l + r) >> 1
        tmp = cal(ori, mid)
        if tmp < tar:
            l = mid + 1
        else:
            r = mid
    return l if cal(ori, l) == tar else 'Impossible'

def main():
    x, y, tag, r = map(str, input().split())
    r = int(r)
    if tag != '1':
        x, y = y, x
    dictInit()
    
    value = 0
    for c in x:
        value = value * r + w[c]
    
    minAns = 0
    for c in y:
        minAns = max(minAns, w[c] + 1)
    
    print(binarySearch(minAns, int(1E18), y, value))

if __name__ == "__main__":
    main()