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 \$>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 < 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 < 2:
        print "1"
    else:
        ans = treeFactor(1, ans)
        ans = convert(ans, b)
        ans = removeZ(ans)
        k = len(ans)
        if k < 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 st

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.

StackExchange Code Review Q#145532, answer score: 3