c - 计算32位int的阶乘（模素数）比C中的O（n）更快？

Question

可能重复：
计算 n 的快速方法！mod m 其中 m 是素数？

让：

int k = 99999989;

k是一个素数。

给定一些 (32-bit) int x，我们要计算 x 阶乘 mod k。(x! % k)

一种方法如下：

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) 空间。

factmk在小于或等于 O(logx) 的空间中，是否有一种渐近更快的方法可以在直接 C 中实现？如果是，那是什么？如果没有，草图证明。

Answer 1

这不是一般的答案，但作为一种特殊情况，如果x = k-1，您可以使用威尔逊定理

(x)! = -1 mod k

或者

(p-1)! = -1 mod p