在C中計算比O（n）更快的32位int的階乘（mod prime）？

可能重複：
Fast way to calculate n! mod m where m is prime?在C中計算比O（n）更快的32位int的階乘（mod prime）？

讓：

int k = 99999989;

k是一個素數。

給定一些（32位）int x，我們要計算x因子模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直C在小於或等於O（logx）空間？如果是，那是什麼？如果不是，草圖證明。

來源

2012-06-09 Andrew Tomazos

可能移動到http：//math.stackexchange。 COM？在那邊有一些驚人的嗖嗖聲，你可以說太多.. –

那麼，如果'n> = k'，那麼'n！％k == 0'，所以它是O（1）;） –

假設查找表超出了問題:-P – will

這不是一般的答案，但作爲一個特殊的情況下，如果x = k-1，您可以使用Wilson's theorem

(x)! = -1 mod k

或

(p-1)! = -1 mod p

來源

2012-06-09 20:07:59 Brian

在C中計算比O（n）更快的32位int的階乘（mod prime）？

回答

相關問題