algorithm - n!模 m , a^p 模 m

Question

是否有更快的算法来计算 (n! modulo m)。在每个乘法步骤都比减少更快。并且有没有比左右二元法更快的算法来计算 (a^p modulo m)。

这是我的代码:n!模数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;
}

Answer 1

现在 a^n mod m 是一个 O(logn)，它是 Modular Exponentiation算法。

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