Submission #3745496

---

Source Code Expand

x = [[]]
n = int(input())
while n % 2 == 0:
    n //= 2
while n % 5 == 0:
    n //= 5

if n == 1:
    print(1)
else:
    s = 10 % n
    for i in range(10):
        x[0].append(s)
        if s == 1:
            break
        s *= 10
        s %= n
    flg = 0
    for i in range(n):
        x.append([])
        for y in x[i]:
            for z in x[0]:
                w = (y+z) % n
                if w == 0:
                    print(i+2)
                    flg = 1
                    break
                if w not in x[i+1]:
                    x[i+1].append(w)
                    
            if flg > 0:
                break
        if flg > 0:
            break

Submission Info

Judge Result