Otro problema de Divisores 2.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

FrankHG, eblabrada, Maite, Marco_Escandon

Problem type

Se le da una arreglo de $n$ ~n~ números enteros positivos.
Su tarea es encontrar dos números enteros de tal manera que su máximo común divisor es tan grande como sea posible.

Entrada

La primera línea de entrada tiene un entero $n$ ~n~ $(2 \le n \le 2 \leq 10^5)$ ~(2 \le n \le 2 \leq 10^5)~: el tamaño de la matriz.
La segunda línea tiene $n$ ~n~ enteros $,x_2,\ldots,x_n$ ~,x_2,\ldots,x_n~ $1 \le x_i \le 10^6$ ~1 \le x_i \le 10^6~: el contenido del arreglo.

Salida

Imprime un entero: el máximo común divisor de los dos números.

Ejemplo de Entrada

5
3 14 15 7 9

Ejemplo de Salida

Explicacion: La respuesta es $7$ ~7~, el maximo comun divisor de $14$ ~14~ y $7$ ~7~ es $7$ ~7~ y el maximo comun divisor de cualquier otro par de elementos es menor que $7$ ~7~.

Comments

2

DaveA55 commented on Jan. 21, 2025, 6:12 p.m.

Alguien me podria dar una idea de como se resuelve este problema? :)

2

eblabrada commented on Jan. 22, 2025, 5:07 a.m.

Puedes usar una criba de divisores para encontrar el máximo entero positivo $d$ ~d~ que divide a al menos dos enteros.