與模量爲大範圍計算階乘給出溢出

我試圖計算階乘對於整數範圍（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。我無法得到溢出的位置以及如何糾正它？謝謝。

來源

2013-08-23 pranay

沒有溢出，結果是正確的。

109546051211 = 186583 * 587117

所以對於所有n >= 587117，我們有n! % 109546051211 = 0。

來源

2013-08-23 19:23:54

你能解釋它是如何爲零的嗎？一些它對我來說不是很直觀。 –

模數是這裏兩個不同素數的乘積，讓我們說'm = p * q'用'p，q'素數和'p = q'，我們都看到'n！ = 1 * 2 * ... * p * ... * q * ... * n'包含'p'和'q'作爲因子，所以'n！'是'p * q的倍數= m'，即'n！％m'是'0'。 –

非常感謝你，我現在明白了。 –

與模量爲大範圍計算階乘給出溢出

回答

相關問題