En la mayoría de las competencias de programación, debemos responder el resultado en 10^9+7 módulo. La razón detrás de esto es que, si las restricciones del problema son números enteros grandes, solo los algoritmos eficientes pueden resolverlos en un tiempo limitado permitido.
Qué es la operación de módulo:
El resto obtenido después de la operación de división en dos operandos se conoce como operación de módulo. El operador para realizar la operación de módulo es ‘%’ . Por ejemplo: a % b = c lo que significa que cuando a se divide por b da el resto c, 7%2 = 1, 17%3 = 2.
¿Por qué necesitamos módulo:
- La razón de tomar Mod es evitar desbordamientos de enteros. El tipo de datos entero más grande en C/C++ es un int largo largo sin signo , que es de 64 bits y puede manejar enteros de 0 a (2^64 – 1). Pero en algunos problemas en los que la tasa de crecimiento de la producción es muy alta, este rango alto de largo largo sin signo puede ser insuficiente.
Supongamos que en una variable de 64 bits ‘A’, se almacena 2^62 y en otra variable de 64 bits ‘B’, se almacena 2^63. Cuando multiplicamos A y B, el sistema no da un error de tiempo de ejecución ni una excepción. Simplemente hace algunos cálculos falsos y almacena el resultado falso porque el tamaño de bits del resultado viene después de que la multiplicación se desborda.
- En algunos de los problemas, para calcular el resultado se necesita módulo inverso y este número ayuda mucho porque es primo. Además, este número debe ser lo suficientemente grande, de lo contrario, las técnicas inversas modulares pueden fallar en algunas situaciones.
Por estas razones, quienes plantean problemas requieren dar la respuesta como resultado del módulo de algún número N.
Hay ciertos criterios de los que depende el valor de N:
- Debe ser lo suficientemente grande como para caber en el tipo de datos entero más grande, es decir, se asegura de que no haya desbordamiento en el resultado.
- Debería ser un número primo porque si tomamos mod de un número por Prime, el resultado generalmente está espaciado, es decir, los resultados son resultados muy diferentes en comparación con mod el número por no primo, es por eso que los primos generalmente se usan para mod.
10^9+7 cumple ambos criterios. Es el primer número primo de 10 dígitos y también cabe en el tipo de datos int. De hecho, cualquier número primo menor de 2^30 estará bien para evitar posibles desbordamientos.
Cómo se usa el módulo:
algunas propiedades distributivas del módulo son las siguientes:
- ( un + segundo ) % c = ( ( un % c ) + ( segundo % c ) ) % c
- (un * segundo) % c = ( ( un % c ) * ( segundo % c ) ) % c
- (a – b) % c = ( ( a % c ) – ( b % c ) ) % c
( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c
Por lo tanto, módulo es distributivo sobre +, * y – pero no sobre / [Consulte División modular para obtener más detalles]
NOTA: El resultado de ( a % b ) siempre será menor que b.
En el caso de los programas de computadora, debido al tamaño de las limitaciones variables, realizamos el módulo M en cada etapa intermedia para que nunca ocurra un desbordamiento de rango.
Example: a = 145785635595363569532135132 b = 3151635135413512165131321321 c = 999874455222222200651351351 m = 1000000007 Print (a*b*c)%m. Method 1: First, multiply all the number and then take modulo: (a*b*c)%m = (459405448184212290893339835148809 515332440033400818566717735644307024625348601572) % 1000000007 a*b*c does not fit even in the unsigned long long int due to which system drop some of its most significant digits. Therefore, it gives the wrong answer. (a*b*c)%m = 798848767 Method 2: Take modulo at each intermediate steps: i = 1 i = (i*a) % m // i = 508086243 i = (i*b) % m // i = 144702857 i = (i*c) % m // i = 798848767 i = 798848767 Method 2 always gives the correct answer.
Función para encontrar el factorial de un gran número usando módulo pero en diferentes posiciones.
C++
unsigned long long factorial(int n)
{
const unsigned int M = 1000000007;
unsigned long long f = 1;
for (int i = 1; i <= n; i++)
f = f * i; // WRONG APPROACH as
// f may exceed (2^64 - 1)
return f % M;
}
// This code is contributed by Shubham Singh
C
unsigned long long factorial(int n)
{
const unsigned int M = 1000000007;
unsigned long long f = 1;
for (int i = 1; i <= n; i++)
f = f * i; // WRONG APPROACH as
// f may exceed (2^64 - 1)
return f % M;
}
Java
static long factorial(int n)
{
const long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = f * i; // WRONG APPROACH as
// f may exceed (2^64 - 1)
return f % M;
}
// This code is contributed by rutvik_56.
Python3
def factorial( n) : M = 1000000007 f = 1 for i in range(1, n + 1): f = f * i # WRONG APPROACH as # f may exceed (2^64 - 1) return f % M # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
static long factorial(int n)
{
const long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = f * i; // WRONG APPROACH as
// f may exceed (2^64 - 1)
return f % M;
}
// This code is contributed by pratham76.
Javascript
function factorial( n)
{
let M = 1000000007;
let f = 1;
for (let i = 1; i <= n; i++)
f = f * i; // WRONG APPROACH as
// f may exceed (2^64 - 1)
return f % M;
}
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C++
unsigned long long factorial(int n)
{
const unsigned int M = 1000000007;
unsigned long long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Shubham Singh
C
unsigned long long factorial(int n)
{
const unsigned int M = 1000000007;
unsigned long long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
Java
static long factorial(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Dharanendra L V.
Python3
def factorial( n) : M = 1000000007 f = 1 for i in range(1, n + 1): f = (f * i) % M # Now f never can # exceed 10^9+7 return f # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
static long factorial(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Dharanendra L V.
Javascript
function factorial( n)
{
let M = 1000000007;
let f = 1;
for (let i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
Se puede seguir el mismo procedimiento para la adición.
(a + b + c) % M es lo mismo que ( ( ( a + b ) % M ) + c ) % M.
Ejecute % M cada vez que se agrega un número para evitar el desbordamiento.
Nota: En la mayoría de los lenguajes de programación (como en C/C++) cuando realiza la operación modular con números negativos da un resultado negativo como -5%3 = -2, pero el resultado después de la operación modular debe estar en el rango de 0 a n-1 significa -5%3 = 1. Entonces, para esto, conviértalo en un equivalente modular positivo.
C++
int mod(int a, int m)
{
return (a % m + m) % m;
}
// This code is contributed by
// Shubham Singh(SHUBHAMSINGH10)
C
int mod(int a, int m)
{
return (a%m + m) % m;
}
Java
static int mod(int a, int m)
{
return (a%m + m) % m;
}
// This code is contributed by
//Shubham Singh(SHUBHAMSINGH10)
Python3
def mod(a, m): return (a%m + m) % m # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
static int mod(int a, int m)
{
return (a % m + m) % m;
}
// This code is contributed by
//Shubham Singh(SHUBHAMSINGH10)
Javascript
function mod( a, m)
{
return (a%m + m) % m;
}
Pero las reglas son diferentes para la división. Para realizar divisiones en módulo aritmético, primero debemos comprender el concepto de módulo inverso multiplicativo.
Módulo inverso multiplicativo (MMI):
El inverso multiplicativo de un número y es z si (z * y) == 1.
Dividir un número x por otro número y es lo mismo que multiplicar x con el inverso multiplicativo de y.
x / y == x * y^(-1) == x * z (donde z es el inverso multiplicativo de y).
En la aritmética normal, el inverso multiplicativo de y es un valor flotante. Ej: El inverso multiplicativo de 7 es 0.142…, de 3 es 0.333… .
En matemáticas, el inverso multiplicativo modular de un entero ‘a’ es un entero ‘x’ tal que el producto ax es congruente a 1 con respecto al módulo m.
ax = 1( mod m)
El resto después de dividir ax por el entero m es 1.
Example: If M = 7, the MMI of 4 is 2 as (4 * 2) %7 == 1, If M = 11, the MMI of 7 is 8 as (7 * 8) % 11 == 1, If M = 13, the MMI of 7 is 2 as (7 * 2) % 13 == 1.
Observe que el MMI de un número puede ser diferente para diferentes M.
Entonces, si estamos realizando aritmética de módulo en nuestro programa y necesitamos el resultado de la operación x / y, NO debemos realizar
z = (x/y) % M;
en su lugar, debemos realizar
y_inv = findMMI(y, M); z = (x * y_inv) % M;
Ahora queda una pregunta.. Cómo encontrar el MMI de un número n.
Existen dos algoritmos para encontrar el MMI de un número. El primero es el algoritmo Euclidiano Extendido y el segundo usa el Pequeño Teorema de Fermat .
Puede encontrar ambos métodos en el enlace dado:
Inverso multiplicativo
modular Encontrar inversos multiplicativos modulares también tiene aplicaciones prácticas en el campo de la criptografía, es decir, la criptografía de clave pública y el algoritmo RSA . Un beneficio para la implementación informática de estas aplicaciones es que existe un algoritmo muy rápido (el algoritmo euclidiano extendido) que se puede utilizar para el cálculo de inversos multiplicativos modulares.
Referencias:
https://www.quora.com/Qué-exactamente-es-print-it-modulo-10-9-+-7-in-competitive-programming-websites
https://discuss.codechef.com/questions/4698 /use-of-modulo-1000007-in-competitions
https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/ Akash Gupta
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA