Last five non-zero digits of a factorial in base b This HackerRank problem (based on Project Euler problem 160) says:


  For any \$n\$, let \$f_b(n)\$ be the last five digits before the trailing zeroes in \$n!\$ written in base \$b\$.
  
  For example,
  
  \$9! = 362880\$ so \$f_{10}(9)=36288\$
  \$10! = 3628800\$ so \$f_{10}(10)=36288\$
  \$20! = 2432902008176640000\$ so \$f_{10}(20)=17664\$
  
  Input format
  
  First line of each file contains two numbers: \$b\$ (base) and \$q\$ (number of queries). \$q\$ lines follow, each with an integer \$n\$ written in base \$b\$.
  
  Constraints
  
  \$2 \le b \le 36\$
  \$1 \le q \le 10^5\$
  \$0 \le n \le 10^{18}\$
  Every character in \$n\$ is a valid digit in base \$b\$ (0-9, A-Z for values \$&gt;9\$)
  
  Output Format
  
  Output \$q\$ lines. On each line print exactly 5 digits in base \$b\$ - the answer to the \$i\$-th query. If for some \$n\$, \$n!\$ contains fewer than 5 digits, put the corresponding number of leading zeroes before the answer.


I believe the code works:

def treeFactor(low, high):
    if low + 1 &lt; high:
        mid = (high+low) // 2
        return treeFactor(low, mid) * treeFactor(mid + 1, high)
    if low == high:
        return low
    return low * high

def convert(num,b,numerals="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    return ((num == 0) and numerals[0]) or (convert(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

def removeZ(ans):
    while ans[-1] == "0":
        ans = ans[:-1]
    return ans[-5:]

b, q = raw_input().split(" ")
b = int(b)
q = int(q)

for _ in xrange(q):
    ans = int(str(raw_input()), 10)
    if ans &lt; 2:
        print "1"
    else:
        ans = treeFactor(1, ans)
        ans = convert(ans, b)
        ans = removeZ(ans)
        k = len(ans)
        if k &lt; 5:
            ans = (5 - k * "0").join(ans) 
        print ans


However, it doesn't run fast enough to pass the tests. I changed the factorial method and tried to cut down on str() conversions, using xrange() and so on, but it still isn't efficient enough. Can you see any bottlenecks, or methods that could be improved further (without the use of specialist packages like NumPy).

(on a slight side note, would it be possible to perform the factorial method on numbers without converting them to base 10, while maintaining efficiency?)
Note that the constraint in this problem is \$n \leq 10^{18}\$. In other words, the factorials you are calculating can be as large as \$10^{18}!\approx 10^{1.7\cdot 10^{18}}\$. In other words, if you aren't running into a time limit, you will most likely run into a memory limit. 

Your function treeFactor calculates:


\$10000!\$ in 0.06 seconds
\$100000!\$ in 2.57 seconds
\$200000!\$ in 9.34 seconds
\$400000!\$ in 29.73 seconds
\$1000000!\$ in 129.58 seconds


In other words, even \$1000000!\$ can't be calculated within the time limit. Futher, \$(10^7)!\$ will probably take at least an hour, \$(10^8)!\$ will probably take several days. Even with a lot of optimizations to calculating factorials, it isn't going to make it, unfortunately. Further, I can't think of a faster method now (I tried a few things, but I got recursion limit exceeded). 

For this problem, you only need the last five non-zero digits. For this, you'll need to do a few things with modular arithmetic. Only read the text under the spoiler if you want more hints. 


   For example, create an array with the five last non-zero digits. Take away all factors that cause a factor of the base \$b\$. Also, note that multiplying by a number larger than \$10^5\$ is the same as multiplying by the same number modulo \$10^5\$. 


I will not write the solution for you. This problem is quite hard - considering that only four people solved it out of over a hundred attempts. I do not know whether this solution is fast enough (also because there is no time limit specified, and because I didn't code it), but it should at least run within a couple of minutes, if you optimalize enough. The calculation of \$10^{18}!\$ can't be done with any method in any reasonable time.