Manera rápida de calcular n! mod m donde m es primo?
Tenía curiosidad si había una buena manera de hacer esto. Mi código actual es algo como:
def factorialMod(n, modulus):
ans=1
for i in range(1,n+1):
ans = ans * i % modulus
return ans % modulus
¡Pero parece bastante lento!
¡Tampoco puedo calcular n! y luego aplica el módulo primo porque a veces n es tan grande que n! simplemente no es factible calcular explícitamente.
También me encontré conhttp: //en.wikipedia.org/wiki/Stirling%27s_approximatio y me pregunto si esto se puede usar aquí de alguna manera.
O, ¿cómo podría crear una función recursiva y memorable en C ++?