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);
}

ただし、上記の print ステートメントでは value = 0 が返されます。実際、すべての n >=587117 について、 factorial[n]%MOD の値を 0 として取得します。オーバーフローがどこにあるのか、それを修正する方法がわかりません。ありがとう。

Answer 1

オーバーフローはなく、結果は正しいです。

109546051211 = 186583 * 587117

だから、すべてのためにn >= 587117、私たちは持っていn! % 109546051211 = 0ます。