algorithm - Calculate this factorial term in C++ with basic datatypes -


i solving programming problem, , in end problem boils down calculating following term:

n!/(n1!n2!n3!....nm!) n<50000 (n1+n2+n3...nm)<n 

i given final answer fit in 8 byte. using c++. how should calculate this. able come tricks nothing concrete , generalized.

edit: not use external libraries.

edit1 : added conditions , result 64 bit int.

if result guaranteed integer, work factored representation.

by theorem of legendre, can express these factorials sequence of exponents of primes in range (2,n).

by deducting exponents of factorials in denominator in numerator, obtain exponents whole quotient. computation reduce product of primes never overflow 8 bytes.

for example,

25! = 2^22.3^10.5^6.7^3.11^2.13.17.19.23 15! = 2^11.3^6.5^3.7^2.11.13 10! = 2^8.3^4.5^2.7 

yields

25!/(15!.10!) = 2^3.5.11.17.19.23 = 3268760 

the exponents of, say, 3 found by

25/3 + 25/9 = 10 15/3 + 15/9 = 6 10/3 + 10/9 = 4 

Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -