[PYTHON] AtCoder Je ne sais pas journal_2 ABC148E

introduction

Depuis la création de D, j'ai pensé que je devrais également jeter un œil à E, alors je me demande s'il existe une formule trop difficile à voir à première vue. J'ai pensé et essayé. De la conclusion, je n'ai pas du tout compris. C'est le problème E ... Jusqu'à ce que vous étudiez correctement les bases de l'algorithme, vous pourrez peut-être faire de votre mieux jusqu'à ce que D. Le problème vient du problème E de ABC148. Ce qui suit est une citation.

E - Double Factorial Pour un entier n supérieur ou égal à 0, définissez f (n) comme suit: f (n) = 1 (lorsque n <2) f (n) = nf (n − 2) (lorsque n ≥ 2) Étant donné l'entier N. Trouvez combien de 0 suivent lorsque f (N) est écrit en notation décimale.

Pensées

① Pour le moment, pensez-vous au nombre de 0 à la fin? C'est assez stupide pour être gêné de regarder en arrière et d'écrire. On vient de me parler du montant du calcul hier ...

Première fois

import re
n = int(input())
i=n-2
while i >= 2:
    n *= i
    i -= 2
    ans = re.search('0+$' , str(n))
print(0 if n%10 !=0 or n < 2 else len(str(n))-ans.start())

C'était TLE. J'ai refait la même erreur ... stupide. Je suis désolé d'avoir surchargé inutilement le serveur. J'ai pris la peine d'étudier les expressions régulières, et j'ai immédiatement utilisé l'opérateur ternaire que j'avais appris.

Deuxième fois

① Si vous commencez par un nombre impair, il n'y aura pas de 10 ou de merde. (2) Puisque 5 n'apparaît pas, seul le nombre de 10 qui apparaît est correct. Je l'ai remarqué maintenant. Est-ce l'extrême de la stupidité?

import re
n = int(input())
ans=0
#Poire quand c'est bizarre et quand c'est trop petit
if n % 2 !=0 or n < 10:
    print(0)
else:
    while n >= 10:
        #Pour le moment, réduisez-le à un multiple de 10.
        if n % 10 != 0:
            n -= 2
        #Diminuez de 10 et additionnez en comptant les 0 derniers
        else:
            z = re.search('0+$' , str(n))
            ans += len(str(n)) - z.start()
            n -= 10


    print(ans)

C'est TLE. Il a été réduit il y a quelque temps! Je me demandais si je pouvais y aller, mais je pense que je pourrais le raccourcir. Il va de soi que le nombre de 0 a une régularité. Je ne sais pas du tout. Mise en conserve

Réponse de l'homme fort (Tsuyobito)

―― La réponse est de diviser par 2 et de continuer à ajouter le quotient divisé par 5 [^ 1]

Pourquoi? !! Je ne sais pas du tout. Programmeur, le QI est de 300 [^ 2]? ?? ?? Je me demande si c'est la base d'une sorte d'algorithme. J'étudierai correctement l'algorithme.

(Une addition)

――Lorsque 5 apparaît dans la fraction, 0 augmente à nouveau avec 2 inclus dans l'entourage pair. ―― Puisque le nombre impair est exclu, 5 apparaît dans la fraction lorsque 2 * 5 ^{i </ sup> ――Vous devez donc compter chaque fois que 2 * 5 i </ sup> apparaît.}

→ Continuez à diviser par 5 ou n // 2 * 5 Continuez jusqu'à ^{i </ sup> Je vois!}

[^ 1]: Il y en avait plusieurs autres, mais c'était celui qui semblait me mâcher le plus. [^ 2]: Il y a probablement environ IQ5000 de personnes fortes qui se retrouvent sur une seule ligne.