c - 计算n!当m不是素数时使用mod m

我读了很多计算n的好算法但当m是质数时，它们通常是有效的我想知道当M不是素数时，是否存在一些好的ALGO。如果有人能写出ALGO的基本功能，我会有所帮助。我一直在使用。

long long factMOD(long long n,long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        for (long long i=2, m=n%mod; i<=m; i++)
        res = (res * i) % mod;
        if ((n/=mod)%2 > 0)
        res = mod - res;
    }
    return res;
}

但当我试图打印factmod（4，3）偶数时得到了错误的答案。此算法的来源是：
http://comeoncodeon.wordpress.com/category/algorithm/

最佳答案

这就是我想出来的：

#include <stdio.h>
#include <stdlib.h>

unsigned long long nfactmod(unsigned long long n, unsigned long long m)
{
    unsigned long long i, f;
    for (i = 1, f = 1; i <= n; i++) {
        f *= i;
        if (f > m) {
            f %= m;
        }
    }
    return f;
}

int main(int argc, char *argv[])
{
    unsigned long long n = strtoull(argv[1], NULL, 10);
    unsigned long long m = strtoull(argv[2], NULL, 10);

    printf("%llu\n", nfactmod(n, m));

    return 0;
}

而这个：

h2co3-macbook:~ h2co3$ ./mod 1000000 1001001779
744950559
h2co3-macbook:~ h2co3$

在几秒钟内运行。

关于c - 计算n!当m不是素数时使用mod m，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14802566/