题解 | #[NOIP1999]回文数#

# 任意进制转换为10进制数
def To10(x, y):
    x = int(x)
    dic = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,
           'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}
    s = 0
    for i in range(len(y)):
        s += dic[y[i]]*x**(len(y)-i-1)
    return s


# 将十进制数转换为任意进制数
def ToAny(x, y):
    x = int(x)
    y = int(y)
    dic = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9',
           10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F'}
    li = []
    while int(y) >= x:
        y, mod = divmod(y, x)
        li.append(dic[mod])
    li.append(dic[y])
    li.reverse()
    return list(''.join(li))


def reverse(x):
    return x[::-1]


if __name__ == '__main__':
    n = input()
    m = input()
    step = 0
    for i in range(1, 31):
        a = ToAny(n, To10(n, m) + To10(n, reverse(m)))
        if a == a[::-1]:
            step = i
            break
        else:
            m = a
    if step > 0:
        print(f'STEP={step}')
    else:
        print('Impossible!')