Расчет n! mod m, когда m не является простым

Question

Я прочитал много хорошего algos, чтобы вычислить n! mod m, но они обычно были действительными, когда m было простым. Я хотел бы знать, существует ли хорошие алго если мин не первична .Я бы полезно, если кто может написать основную функцию алго too.I использовали

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/

Answer 1

Это то, что я придумал:

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

работает в доли секунды.

Answer 2

Основной алгоритм справедлив для любого значения m:

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

и простой оптимизации является то, что вы можете выручить рано и возвращать 0, когда product становится равным 0. Вы также можете вернуть 0 в начале, если n> m, так как это гарантирует, что n! является кратным m.