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

я попытался вычислить факториал для диапазона целых чисел (2‹=n‹=10^7) и по модулю следующим образом:

MAXN = 10000000
typedef unsigned long long ULL;
ULL MOD =  109546051211ULL;
ULL factorial[MAXN+1];

void preFact()
{
    factorial[0] = factorial[1] = 1;
    int i;
    for(i = 2;i<=MAXN;i++)
    {
        ULL temp = factorial[i-1]%MOD;
        ULL temp2 = i%MOD;

        temp = (temp*temp2)%MOD;
        factorial[i] = temp;
    }
    printf("%llu %d\n",factorial[i-1],i);
}

Однако приведенный выше оператор печати дает значение = 0 . Фактически для всех n >= 587117 я получаю значение factorial[n]%MOD как 0 . Я не могу понять, где переполнение и как его исправить? Спасибо.


math factorial
person pranay    schedule 23.08.2013    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Переполнения нет, результат правильный.

109546051211 = 186583 * 587117

поэтому для всех n >= 587117 у нас есть n! % 109546051211 = 0.

person Daniel Fischer    schedule 23.08.2013
comment
Можете ли вы объяснить, как это ноль? как-то мне это не очень интуитивно понятно. - person Nitin Jaiman; 19.01.2015
comment
Модуль — это произведение двух различных простых чисел, скажем, m = p*q с p,q простыми числами и p < q. Затем для каждого n >= q мы видим, что n! = 1*2*...*p*...*q*...*n содержит оба, p и q, как множители, поэтому n! кратно p*q = m, т. е. n! % m равно 0. - person Daniel Fischer; 19.01.2015
comment
Большое спасибо, теперь я понял. - person Nitin Jaiman; 19.01.2015