MCD


Submit solution

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

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

Se tiene una secuencia S de N (1 \leq N \leq 200 000) números enteros positivos S1, S2, S3, S4,..., SN (1 \leq S_i \leq 1000). 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 (S1, S2), MCD (S2, S3), ..., MCD (SN, S1)

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

  • Determine si es posible cuántas veces se tiene que reemplazar la secuencia completa para obtener una secuencia formada por solamente números 1.

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

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

Comments

There are no comments at the moment.