Submission #55866788

---

Source Code Expand

n = input()
if n == n[::-1] and '0' not in n:
    print(n)
    exit(0)
n = int(n)
dp = {}
dp[1] = (1,1)
cand = []
mid = [1, ]
for i in range(2, int(n**0.5)+1):
    si = str(i)
    j = int(si[::-1])
    if n % i == 0:
        if n // i % j == 0 and '0' not in si:
            cand.append((i,j))
        if i == j and '0' not in si:
            mid.append(i)
        q = n // i
        if q != i and str(q) == str(q)[::-1] and '0' not in str(q):
            mid.append(q)

def calc(x):
    if x in dp:
        return dp[x]
    dp[x] = None
    for a, b in cand:
        if x % (a * b) == 0 and calc(x // (a * b)):
            dp[x] = (a, b)
            break
    return dp[x]

def get(x, center):
    if x == 1:
        return center
    a, b = dp[x]
    return str(a) + "*" + get(x // a // b, center) + "*" + str(b)

for m in mid:
    if calc(n // m):
        print(get(n // m, str(m)))
        exit(0)
print(-1)

Submission Info

Judge Result