Faites un nombre de 7 de manière simple et divisez par K pour déterminer s'il devient 0. Puisque K est inférieur à 10 $ ^ 6 $, organisez 7 jusqu'à cette plage. Si vous pensez que 7 est aligné pour 10 $ ^ 6 $, bien sûr TLE
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)
Il semble que vous devriez implémenter quelque chose qui coûte cher en calcul. L'écriture ordinaire consiste à ajouter trop de 0 et à continuer le calcul jusqu'à ce qu'il soit divisible (jusqu'à ce que vous en ayez envie), mais à la place, ajoutez 7. Par exemple, $ 10 \ div 8 $ ressemblerait normalement à ceci:
10 \div 8 = 1 \,pas vraiment\, 2 \\
20 \div 8 = 2 \,pas vraiment\, 4 \\
40 \div 8 = 5 \,pas vraiment\, 0 \\
répondre: \,1.25
Cela se fait comme suit.
10 \div 8 = 1 \,pas vraiment\, 2 \\
(20 + 7) \div 8 = 3 \,pas vraiment\, 3 \\
(30 + 7) \div 8 = 4 \,pas vraiment\, 5 \\
...
Quand je l'implémente en Python, cela ressemble à ceci. (Lorsque K = 101 dans l'exemple numérique) C'est rapide car chaque calcul est trop. ~~ Si c'est 10 $ ^ 6 $ fois, c'est acceptable. ~~ (Ajout: D'après le commentaire, il semble que K fois suffit car il ne peut y avoir que K rues en dessous de K. Merci!)
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
"""
Enfin AC ci-dessous
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