MCD


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Se tiene una secuencia S de N números enteros positivos S_1, S_2, S_3, S_4,..., S_N. Luego, cada número de la secuencia se reemplaza por el máximo común divisor (MCD) de él mismo y el siguiente número en la secuencia. El último número de la secuencia se reemplaza por el máximo común divisor de él mismo y el primero:

MCD(S_1, S_2), MCD(S_2, S_3), ..., MCD(S_N, S_1)

Esta operación se repite varias veces intentando que todos los números en la secuencia sean 1, aunque algunas veces esto no es posible.

Por ejemplo, la secuencia 4, 12, 3, 9 se tendría que reemplazar 3 veces:

4, 3, 3, 1

1, 3, 1, 1

1, 1, 1, 1

Tarea

Escriba un programa que:

  • lea desde la entrada estándar la secuencia S,
  • determine si es posible cuántas veces se tiene que reemplazar la secuencia completa para obtener una secuencia formada por solamente números 1,
  • escriba hacia salida estándar el valor correspondiente al número de veces ó -1 en caso contrario.

Entrada

Línea 1: un número entero N,

Línea 2: N números enteros positivos separados por espacios, representando la secuencia S.

Salida

Contiene un solo número entero, el número de veces que se tiene que reemplazar la secuencia completa para obtener una secuencia de solamente números 1. Si no es posible escriba simplemente \(–1\).

Ejemplo de Entrada

 4
 4 12 3 9

Ejemplo de Salida

3

Consideraciones

1 \le N \le 200 000

1 \le S_i \le 1 000 para todo 1 \le i \le N


Comments

There are no comments at the moment.