math - 用模数计算大范围的阶乘会溢出

Question

我尝试计算一系列整数 (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);
}

但是上面的打印语句给出了 value = 0 。事实上，对于所有 n >=587117 我得到 factorial[n]%MOD 的值为 0 。我不知道溢出在哪里以及如何纠正它？谢谢。

Answer 1

没有溢出，结果正确。

109546051211 = 186583 * 587117

所以对于所有 n >= 587117，我们有 n! % 109546051211 = 0。