puzzle contents
Contents
raw puzzle

Original Problem

Manasa was sulking her way through a boring class when suddenly her teacher singled her out and asked her a question. He gave her a number n and Manasa has to come up with the smallest number m which contains atleast n number of zeros at the end of m!. Help Manasa come out of the sticky situation.

Input Format 
The first line contains an integer T i.e. the number of Test cases. 
Next T lines will contain an integer n.

Output Format 
Print smallest such number m.

Constraints 
1 ≤ T ≤ 100 
1 ≤ n ≤ 1016

Sample Input

3
1
2
3

Sample Output

5
10
15

Explanation

  1. As 4! = 24 and 5! = 120, so minimum value of m will be 5.
  2. As 9! = 362880 and 10! = 3628800, so minimum value of m will be 10.
  3. As 14! = 87178291200 and 15! = 1307674368000, so minimum value of m will be 15.

Solution

We are looking for the smallest mm such that m!0(mod10n)m!\equiv 0\pmod{10^n}. Since the number of fives as a prime factor of 10 in 10n10^n is equivalent to the number in 5n5^n, we can equivalently write m!0(mod5n)m!\equiv 0\pmod{5^n}. That means there exists a number rr for the rest such that m!=r5nm! = r \cdot 5^n. To come up with a reasonable upper bound, we ignore rr and say m!101016m! \leq 10^{10^{16}} and solve for mm by taking the log(m!)1016i=1mlogi1016\log({m!}) \leq 10^{16}\Leftrightarrow\sum\limits_{i=1}^m\log{i}\leq 10^{16} from which the upper bound mu=694100859679691m_u=694100859679691 follows. This upper bound is not enough, since it covers only the number of trailing zeros, so guessing the real upper bound to be 100 times larger than the calculated one sounds okay. Since the number of zeros grows with mm, we can now do a binary search or even better an interpolation search on a function that counts the trailig zeros by canceling out 5,25,125,...5, 25, 125, ... as derived before and the large upper bound doesn't harm that much anymore. Hence #0(m)=i=1m5i\#_0(m) = \sum_{i=1}^{\infty} \left\lfloor\frac{m}{5^i}\right\rfloor can be implemented as

def countTrailingZeros(m)
  s = 0
  p = 5
  while p <= m
    s+= m / p
    p*= 5
  end
  return s
end

Or stated recursively:

def countTrailingZeros(m)
  return 0 if m == 0
  return m / 5 + countTrailingZeros(m / 5)
end

Implementing a binary search can then look as follows (yes, we could use ruby's bsearch method, too):

gets.to_i.times {
  n = gets.to_i
  r = -1
  l = 0
  u = 69410085967969100
  while l <= u
    m = (l + u) / 2

    if n <= countTrailingZeros(m)
      r = m
      u = m - 1
    else
      l = m + 1
    end
  end
  puts r
}