n的阶乘对m取模，a的p次方对m取模。

Question

有没有更快的算法来计算 (n! 模 m)。比每个乘法步骤都进行归约更快的算法。 还有，有没有更快的算法来计算 (a^p 模 m)，比右-左二进制方法更好。

这是我的代码： n! mod m

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

a^p mod m

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

- user1131274

---

可能是重复的问题：[快速计算n！mod m，其中m是素数？]（https://dev59.com/MWkw5IYBdhLWcg3wrsdS） - Tacet

Answer 1

现在 a^n mod m 是一个 O(logn) 的算法，这就是模指数算法。

现在对于另外一个算法，n! mod m，你提出的算法显然是 O(n) 的，所以很明显第一个算法更快。

- st0le

---

难道没有任何数论结果可以使这更好吗？ - user1131274

@user1131274，我尝试了一种替代方法来计算n! mod m，但速度并没有提升很多。我将n分解为其素因数的乘积n = p1^e1 p2^e2...pn^en，然后使用powMod(第一个算法)来计算pi^ei mod m，并将它们相乘...可能有更好的方法，但我还不知道。 - st0le

a^n mod m和n！mod m是两个根本不同的问题，我很困惑你为什么把这两种解决方案进行比较。 - Paul Lo

Answer 2

计算 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。

我不确定阶乘是否有类似的模运算，但一个好的起点是威尔逊定理。此外，您应该为m <= n设置一个测试，在这种情况下，n！mod m = 0。

- PengOne

Answer 3

对于第一次计算，只有当 ans > m 时才需要考虑模运算符：

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

对于第二次计算，使用(p & 1) != 0可能比使用p%2!=0要快得多（除非编译器识别此特殊情况并为您执行）。然后同样适用于避免使用%运算符，除非必要。

- Ted Hopp

---

当我们进行微小的优化时，if(ans > m) ans -= m 会更快。 - st0le

@st0le但是我们在进行乘法，因此ans可能比2m大。 - Daniel Fischer

@DanielFischer，对不起！你说得对，显然 while(ans > m) ans-=m 也会更慢。因此我谨慎地撤回我的评论。 :) - st0le

那将是if(ans >= m) ... 但是，假设i! mod m相对均匀分布，模操作不必要的概率只有约为1/i。分支可能会造成更多的伤害而非好处。 - Jeffrey Sax

@JeffreySax - 是的，我考虑过这个问题，但没有分析过。我认为减法比取模要便宜得多。但也许并不是那么便宜。 - Ted Hopp

嘿伙计们，在上述情况下有没有任何数论结果可以派上用场，因为我正在处理非常大的数字。 - user1131274