¿Cuál es la necesidad de la instrucción ans = (ans + mod) % mod en este programa?
Suponga que mod = 10^9+7 . Esta función está calculando a elevado a b bajo la operación mod en complejidad O(log(n)):
long long power(long long a, long long b) { if (b == 0) return 1ll; long long ans = power(a, b/2); ans = (ans * ans) % mod; ans = (ans + mod) % mod; if(b % 2 == 1) ans = (ans * a) % mod; ans = (ans + mod) % mod; return ans; }El uso más común de tal construcción es asegurarse de que el resultado no sea negativo. El operator% se comporta de manera diferente para argumentos positivos y negativos: por ejemplo, 4%3==1 , pero (-2)%3==-2 , mientras que podría esperar (-2)%3==1 y (-2)/3==-1 , que es matemáticamente más correcto.
Este comportamiento a menudo puede causar problemas cuando se usa aritmética modular, y este truco de agregar mod se emplea a menudo para obtener el resultado no negativo matemáticamente más correcto. En lugar de simplemente escribir a%b , si a puede ser negativo, uno escribe (a%b+b)%b .
Sin embargo, su uso en el código de su pregunta es extraño. En ese caso, es más fácil asumir que a es positivo antes de llamar a la función power desde el código principal (por ejemplo, al hacer la llamada principal como power((a%mod+mod)%mod, b) ). Probablemente el autor solo quería obtener una garantía adicional de corrección, aunque no era necesaria.