模拟小学除法

模仿10进制转化为2进制的算法, 直接从A进制转化为B进制
其中A进制数字除以B的算法是模仿小学除法(从高位到低位, 依次去除以B)

时间复杂度

O(N)
N为A进制数字的位数

Python 代码

def decode(num):
    if num <= 9:
        return chr(ord("0") + num)
    elif num <= 35:
        return chr(ord("A") + num - 10)
    else:
        return chr(ord("a") + num - 36)

D = {i : decode(i) for i in range(62)}
E = {decode(i) : i for i in range(62)}

def solve(A, B, digitsA):
    digitsB = []
    while digitsA:
        carry = 0
        for i in range(len(digitsA) - 1, -1, -1):
            digitsA[i], carry = divmod(A * carry + digitsA[i], B)
        digitsB.append(D[carry])
        while digitsA and digitsA[-1] == 0:
            digitsA.pop()
    return "".join(digitsB[::-1])



T = int(input())
for _ in range(T):
    A, B, digitsA = input().split()
    A = int(A)
    B = int(B)
    digitsA2 = [E[e] for e in digitsA][::-1]
    digitsB = solve(A, B, digitsA2)
    print(A, digitsA)
    print(B, digitsB)
    print()