Почему значение факториала не помещается даже в QWord?

Question

[Avery007]

Нужно решить задачу, вне формула C=N!/M!*(N-M)!. При значении N=21, значение N! не помещается никуда, пробовал QWord, integer, longint, word, int64, longword ошибки 201 и 215. N и M меньше 50000.
Код:

function Prost(a:QWord):boolean;
var i:int64;
    f:boolean;
begin
if a<2 then f:=false
else
 begin
  f:=true;
  i:=2;
  while (i*i<=a) and f do
  if a mod i=0 then f:=false
  else i:=i+1;
 end;
 Prost:=f;
end;
function fact(k: QWord) : QWord;
var
  p: QWord;
  i: integer;
begin
    p:=1;
    for i:=2 to k do
    begin
       p:=p*i;
  	End;
  	fact:= p;
end;
var
  N, M, C, count : QWord;
  i : integer;
begin
	read(N);
	read(M);
	count:= 0;
	C:= fact(N) div (fact(M) * fact(N - M));
	for i:= 1 to C do
	Begin
		if C mod i = 0 then
		Begin
			if Prost(i) then inc(count);
		End;
	End;
	write(count);
End.

Answer 1

[Pavlo Barmak]

Для хранения очень больших чисел используется длинная арифметика, я думаю вы легко нагуглите готовые библиотеки.

Но что-то мне подсказывает, что в вашем случае нужно какое-то хитрое алгоритмическое решение, ибо факториал от 50000 - это на средненьком железе десяток-второй секунд считать.

Answer 2

[Александр Рулёв]

Если смотреть на эту формулу, то видно, что весь факториал считать не нужно и она немного сокращается (начало факториала N делится на весь факториал M).

C = N! / (M! * (N - M)!)

import math

def combinations(n, m):
    k = n - m
    if k == 0:
        return 1

    result = 1
    for i in range(m + 1, n + 1):
        result *= i

    result //= math.factorial(k)
    return result

print(combinations(30, 25)) # 142506