Search code examples
c++algorithmfactorial

Calculate this factorial term in C++ with basic datatypes

I am solving a programming problem, and in the end the problem boils down to calculating following term:

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

I am given that the final answer will fit in 8 byte. I am using C++. How should I calculate this. I am able to come up with some tricks but nothing concrete and generalized.

EDIT: I would not like to use external libraries.

EDIT1 : Added conditions and result will be definitely 64 bit int.

Solution

  • If the result is guaranteed to be an integer, work with the factored representation.

    By the theorem of Legendre, you can express all these factorials by the sequence of exponents of the primes in the range (2,n).

    By deducting the exponents of the factorials in the denominator from those in the numerator, you will obtain exponents for the whole quotient. The computation will then reduce to a product of primes that will never overflow the 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 are found by

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