1

我已经阅读了很多很好的算法来计算 n！mod m 但它们通常在 m 为 prime 时有效。我想知道当 m 不是素数时是否存在一些好的算法。如果有人也可以编写算法的基本功能，我会很有帮助。我一直在使用

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/

4

2 回答 2

4

基本算法对 的任何值都有效m：

product := 1
for i := 2 to n
    product := (product * i) mod m
return product

一个简单的优化是您可以提前退出并在product变为 0 时返回 0。如果 n > m，您也可以在开头返回 0，因为这保证了 n！是 m 的倍数。

于 2013-02-10T21:08:47.320 回答
3

这就是我想出的：

#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$

在几分之一秒内运行。

于 2013-02-10T21:16:29.970 回答