[PYTHON] AtCoder I don't know diary_2 ABC148E

Introduction

Since D was created, I thought I should take a look at E as well, so I wonder if there is a mathematical formula that is too difficult to see at first glance. I thought and tried it. From the conclusion, I didn't understand at all. This is the E problem ... Until you study the basics of the algorithm properly, you may be able to do your best until D. The problem is from the E problem of ABC148. The following is a quote.

E - Double Factorial For an integer n greater than or equal to 0, define f (n) as follows: f (n) = 1 (when n <2) f (n) = nf (n−2) (when n ≥ 2) Given the integer N. Find how many zeros follow when f (N) is written in decimal notation.

Thoughts

① For the time being, do you think about how many trailing 0s there are? It's stupid enough to be embarrassed to look back and write. I was just told about the amount of calculation yesterday ...

First time

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())

It was TLE. I made the same mistake again ... stupid. I'm sorry for unnecessarily overloading the server. I took the trouble to study regular expressions, and I immediately used the ternary operator I learned.

Second time

① If you start with an odd number, there will be no 10 or shit. (2) Since 5 does not appear, only the number of 10 that appears is ok. I noticed it now. Is it the extreme of stupidity?

import re
n = int(input())
ans=0
#Pear when odd and too small
if n % 2 !=0 or n < 10:
    print(0)
else:
    while n >= 10:
        #For the time being, reduce it to a multiple of 10.
        if n % 10 != 0:
            n -= 2
        #Decrease by 10 and add up by counting the trailing 0s
        else:
            z = re.search('0+$' , str(n))
            ans += len(str(n)) - z.start()
            n -= 10


    print(ans)

This is TLE. It's been reduced a while ago! I was wondering if I could go, but I think I could make it shorter. It is self-evident that the number of 0s has regularity. I don't know at all. Cheat

Answer of a strong man (Tsuyobito)

――The answer is to divide by 2 and continue to add the quotient divided by 5 [^ 1]

why? !! I don't know at all. Programmer, IQ is 300 [^ 2]? ?? ?? I wonder if that is the basis of some kind of algorithm. I will study the algorithm properly.

(Addition)

――When 5 appears in the divisor, 0 increases again with 2 included in the surrounding even numbers. --Since odd numbers are excluded, 5 appears in the divisor when 2 * 5 ^{i </ sup> ――So, you should count every time 2 * 5 i </ sup> appears.}

→ Continue to divide by 5 or n // 2 * 5 Continue to ^{i </ sup> I see!}

[^ 1]: There were several others, but this was the one that seemed to chew most in my brain. [^ 2]: There are probably about IQ5000 of strong people who end up in one line.