重複の可能性:
n を計算する高速な方法! mod m m は素数ですか?
させて：
int k = 99999989;
k素数です。
いくつかの (32 ビット) が与えられint xた場合、x factorial mod k を計算します。（Xのk）
これを行う 1 つの方法は次のとおりです。
int factmk(int x)
{
long long t = 1;
for (long long i = 2; i <= x; i++)
{
t *= i;
t %= k;
}
return (int)t;
};
これには O(x) 時間と O(1) スペースが必要です。
factmkO(logx) 以下のスペースでストレート C に実装する漸近的に高速な方法はありますか? はいの場合、それは何ですか? いいえの場合は、証拠をスケッチします。