Hi everyone, I’m trying to solve problem in which I have to calculate the last non-zero digit of this:
(a1+a2+a3+..+an)!/(a1!*a2!*a3!*..*an!), where 0 ≤ ai ≤ 1000000000 and n ≤ 20.
It's obvious, that the “brutal” counting this is a bad solution (counting the one billion factorial takes too much time and memory). Another solution is an attempt to shorten. I write numerator and denominator is a simplified form (for example: 5!=1*2*3*4*5) and I’m reducing until the denominator = 1, then I’m starting to multiplies (with using my own arithmetic for large numbers) numbers that I got. This solution, in turn, doesn’t work because there is no space in the memory for a sufficiently large array (for the awarding of the numerator and denominator), on the other hand, because even after reducing, the numbers are too big for it to multiply them at the right time (for example, the medium(!) numbers – please take a look at the result: (6000!)/(1000!*2000!*3000!) - Wolfram|Alpha ). Another idea was to calculate the common logarithm of that number, but the solution isn’t valid because of too little precision of long double variable. I have no other ideas for solving this problem, so please help me with it.
Examples:
n=2, a1=11, a2=9
Result: 6 (Last nonzero digit: (20!)/(11!*9!) - Wolfram|Alpha )
n=4, a1=2, a2=5, a3=7, a4=9
Result: 8 (Last nonzero digit: (23!)/(5!*2!*7!*9!) - Wolfram|Alpha )