Make a number in which 7s are lined up obediently, and divide it by K to determine whether it becomes 0. Since K is less than $ 10 ^ 6 $, arrange 7 up to that range. Naturally TLE if you think that 7 is lined up for $ 10 ^ 6 $
K = int(input())
flg = False
for i in range(10 ** 6):
n = int('7' * (i + 1))
if n % K == 0:
flg = True
break
if flg:
print(len(str(n)))
else:
print(-1)
It seems that you should implement something that is long-division. Ordinary long division is to add 0 too much and continue the calculation until it is divisible (until you feel like it), but instead add 7. For example, $ 10 \ div 8 $ would normally look like this:
10 \div 8 = 1 \,not really\, 2 \\
20 \div 8 = 2 \,not really\, 4 \\
40 \div 8 = 5 \,not really\, 0 \\
answer: \,1.25
This is done as follows.
10 \div 8 = 1 \,not really\, 2 \\
(20 + 7) \div 8 = 3 \,not really\, 3 \\
(30 + 7) \div 8 = 4 \,not really\, 5 \\
...
When I implement it in Python, it looks like this. (When K = 101 in the numerical example) It's fast because each calculation is too much. ~~ If it is $ 10 ^ 6 $ times, it is acceptable. ~~ (Addition: From the comment, it seems that K times is enough because there can be only K streets below K. Thank you!)
K = 101
cur = 7
for i in range(100):
mod = cur % K
print(f'{cur} % {K} = {mod}')
if mod == 0:
ans = i + 1
print(f'Answer: {ans}')
break
else:
cur = mod * 10 + 7
"""
(output)
7 % 101 = 7
77 % 101 = 77
777 % 101 = 70
707 % 101 = 0
Answer: 4
"""
Finally AC below
K = int(input())
cur = 7
flg = False
for i in range(10 ** 6):
mod = cur % K
if mod == 0:
ans = i + 1
flg = True
break
else:
cur = mod * 10 + 7
if flg:
print(ans)
else:
print(-1)
Recommended Posts