n！模m，a^p模m

有更快的算法來計算（n！模m）。在每個乘法步驟中減少的速度要快於。而且還是否有更快的算法方式計算（A^P模m），比左右的二進制方法更好。n！模m，a^p模m

這裏是我的代碼： N！模m

ans=1 
for(int i=1;i<=n;i++) 
    ans=(ans*i)%m;

一^ P模m

result=1; 
while(p>0){ 
    if(p%2!=0) 
     result=(result*a)%m; 
    p=(p>>1); 
    a=(a*a)%m; 
}

來源

2012-01-05 user1131274

的[快速的方法來計算n個可能的重複！ mod m其中m是素數？]（http：// stackoverflow。COM /問題/ 9727962 /快的方式對計算正模 - 間 - 其中 - 間是素數） – Tacet 2014-11-11 00:14:07

對於第一個計算，你應該只用mod運算符，如果ans > m麻煩：

ans=1 
for(int i=1;i<=n;i++) { 
    ans *= i; 
    if (ans > m) ans %= m; 
}

對於第二個計算，使用(p & 1) != 0可能會比使用p%2!=0（除非編譯器可以識別這種特殊情況，並會爲你）要快得多。然後，除非必要，否則同樣的評論適用於避免%運營商。

來源

2012-01-05 03:54:27

雖然我們微優化，'如果（ANS>米）ANS - = M'會更快。 – st0le 2012-01-05 03:57:37

@ st0le但我們正在相乘，所以'ans'可以大於'2m'。 – 2012-01-05 04:14:57

@DanielFischer，哈哈！你說得很對，很明顯'while（ans> m）ans- = m'也會變慢。所以我恭敬地收回我的評論。 :) – st0le 2012-01-05 04:39:54

現在的a^n mod m是O(logn)，這是Modular Exponentiation算法。

現在的另外一個，n! mod m，你提出的算法顯然是O(n)，所以，很顯然第一算法更快。

來源

2012-01-05 04:01:20 st0le

它可以在上述情況下，用戶可以任意數量的理論結果are'nt有沒有數論的成果，它可以使這個更好。 – user1131274 2012-01-05 08:51:18

@ user1131274，我嘗試了一種替代方法來計算'n！ mod m「，但速度並不快。我打破了'N'到它的首要因素'N = P1^E1 P2^E2 ... PN^en'然後使用'powMod'（第一算法）來計算圓周率'^ EI模M'再乘以在一起.. 。可能有更好的方法，但我還不知道。 – st0le 2012-01-05 09:12:46

a^n mod m和n！mod m根本上是兩個不同的問題，我很困惑你比較了這兩個解決方案。 – 2015-01-16 14:54:47

標準特技用於計算a^p modulo m是使用連續的正方形。這樣做是爲了擴大p成二進制，說

p = e0 * 2^0 + e1 * 2^1 + ... + en * 2^n

其中(e0,e1,...,en)是二進制（0或1）和en = 1。然後用指數的法律得到以下擴張a^p

a^p = a^(e0 * 2^0 + e1 * 2^1 + ... + en * 2^n) 
    = a^(e0 * 2^0) * a^(e1 * 2^1) * ... * a^(en * 2^n) 
    = (a^(2^0))^e0 * (a^(2^1))^e1 * ... * (a^(2^n))^en

記住，每個ei要麼0或1，所以這些只是告訴你採用何種數字。因此，您需要的唯一計算是：

a, a^2, a^4, a^8, ..., a^(2^n)

您可以通過平方先前的項來生成此序列。既然你想計算答案mod m，你應該首先進行模運算。這意味着你要計算以下

A0 = a mod m 
Ai = (Ai)^2 mod m for i>1

答案是那麼

a^p mod m = A0^e0 + A1^e1 + ... + An^en

因此計算需要log(p)的廣場，並呼籲mod m。

我不能肯定是否有對階乘模擬，而是一個好地方開始尋找將在Wilson's Theorem。另外，您應該對進行測試，在這種情況下n! mod m = 0。

來源

2012-01-05 06:15:04 PengOne

n！模m，a^p模m

回答

相關問題