数 字 论 证 器

114514.py

def cal(s):
    s = s.replace('/', '//')
    try:
        return eval(s)
    except:
        return None


def getx(a, b):  # 直接用 ~- 或者 -~ 把 a 变成 b
    va = cal(a)
    if va == b:
        return a
    if len(a) != 1:
        a = '(' + a + ')'
    if va < b:
        return '-~' * (b - va) + a
    return '~-' * (va - b) + a


num = [1, 1, 4, 5, 1, 4]


def geta(x, l, r, c):  # dfs，x 是当前需要表示的数，l 和 r 是枚举进制的范围，c 是当前还剩几位。其实只是为了构造一个解是用不着 dfs 的，但是这里我们可以得到一个较短的解
    if c == 0:
        if x == num[0]:
            return 1, []
        return abs(x - num[0]) * 2 + 1, []
    ans = 10**100
    for i in range(l, r + 1):
        a = x // i
        b = x % i
        x1, y1 = geta(a, l, r, c - 1)
        x1 += 0 if b == 0 else 2 + b * 2
        x1 += 2 + abs(num[c] - i) * 2
        if x1 < ans:
            ans = x1
            ansp = y1 + [(i, b)]
        a += 1
        b = x - a * i
        x1, y1 = geta(a, l, r, c - 1)
        x1 += 0 if b == 0 else 2 - b * 2
        x1 += 2 + abs(num[c] - i) * 2
        if x1 < ans:
            ans = x1
            ansp = y1 + [(i, b)]
    return ans, ansp


def conans(x, s):  # 用 getx 的结果构造答案
    c = len(s)
    if c == 0:
        return getx(str(num[0]), x)
    u, b = s[-1]
    assert (x - b) % u == 0
    a = (x - b) // u
    return getx(conans(a, s[:-1]) + '*' + getx(str(num[c]), u), x)


def _get(x):  # 求解。在 x^{1/6} 附近枚举每一位的进制。x 较小时可能出问题
    l = 0
    r = 1 << (x.bit_length() + 10) // 6
    assert r**6 > x
    while l + 1 < r:
        mid = (l + r) >> 1
        if mid**6 <= x:
            l = mid
        else:
            r = mid
    a, b = geta(x, l - 2, r + 2, len(num) - 1)
    ans = conans(x, b)
    assert len(ans) == a
    return ans


def get(x):  # 处理负数
    if x < 0:
        return '-(' + _get(-x) + ')'
    return _get(x)


if __name__ == '__main__':
    print(get(1919810))
    print(get(114514))
    print(get(1145))
    print(get(10**12))