Dada una matriz de números y su gcd si un elemento se elimina cómo llegar nueva gcd en tiempo mínimo

Question

Tengo una matriz de números y su gcd si se elimina un elemento de la matriz entonces es posible conseguir el gcd nuevo sin iteración todos los elementos de la matriz.

por ejemplo la matriz es 3 6 6 12 claramente el MCD es 3

ahora si 3 se elimina de la matriz de la nueva matriz se convierte entonces en 6 6 12 y el MCD es 6

Nota: La matriz puede contener Duplicados y cuando el número se elimina entonces sólo una instancia de ese número se elimina de la matriz.

Answer 1

Hay poca esperanza para nada de eso. La razón es muy simple. Para cualquier elección de enteros $a_1,\cdots, a_n$, $gcd$ de la $n+1$ tupla compuesta por los números enteros con $1$ lanzado en, es, claramente, igual a $1$. Que la información no podrá ayudar a que ahora calcular el $gcd$ de los números originales. Así, usted no puede esperar que un procedimiento general para calcular el $gcd$ después de la eliminación de un elemento, a partir de conocer el $gcd$ de la lista original de los elementos (con o sin repetición) que va a ser mejor, a continuación, sólo calcular el $gcd$. Si además se especifican las condiciones de los elementos en la lista, entonces puede ser posible salvar algo de información para que realmente acelerar el proceso, aunque dudo cuánto más eficiente sería este.