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

回答

相关问题