El problema es: dada una lista de números, genera un divisor D tal que el resto tras la división por D sea el mismo para todos los números.
Otra forma de expresarlo es que se le dan [matemáticas] x_1, x_2,…, x_n [/ matemáticas] y se le pide que encuentre [matemáticas] D [/ matemáticas] de modo que
[matemáticas] x_1 \ equiv x_2 \ equiv x_3… \ equiv x_n \ pmod {D} [/ matemáticas]
- ¿Cómo funciona el algoritmo de armonía?
- 1,000 participantes toman un examen que consta de 100 preguntas y 5 opciones por pregunta. ¿Cuál es el mejor enfoque (algoritmo) para encontrar todos los pares posibles de participantes con al menos un 80% de coincidencia en las opciones que eligieron?
- Cómo encontrar el promedio de todos los múltiplos de un número de un rango de números
- ¿Qué es una explicación intuitiva de IDA * (profundización iterativa A *)?
- ¿Cómo analizar la complejidad de caso promedio de un algoritmo? ¿Hay alguna fuente para aprenderlo paso a paso de lo básico?
Si dos números son módulos equivalentes [matemática] D [/ matemática], entonces su diferencia es un múltiplo de [matemática] D [/ matemática].
Eso sugiere el siguiente enfoque: calcular las diferencias entre pares de números y tomar el MCD de esas diferencias. Cada diferencia entre pares será un múltiplo de ese MCD (que bien puede ser 1), por lo que todos los números serán congruentes (es decir, tendrán el mismo resto).
Si calculamos la diferencia para cada par, serían pares [matemáticos] O (n ^ 2) [/ matemáticos], lo que parece indeseable. Por lo tanto, nos gustaría demostrar que esto es innecesario. Suponga que [math] y = \ gcd (x_1 – x_2, x_2 – x_3) [/ math]. Luego, por las propiedades de GCD, [math] y = \ gcd (x_1 – x_2 + (x_2 – x_3), x_2 – x_3) = \ gcd (x_1 – x_3, x_2 – x_3) [/ math]. Por lo tanto, podemos considerar solo pares adyacentes al calcular nuestras diferencias, y terminamos con el mismo MCD como si hiciéramos todos los pares.
