1

n を計算するために多くの優れたアルゴリズムを読みました! mod m ですが、 m が素数の場合は通常有効でした。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

簡単な最適化は、早期に救済し、0になるたびproductに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 に答える