Máximo común divisor para todos los subsegmentos

Go Hard math

Tarea «Máximo común divisor para todos los subsegmentos»

Dado un arreglo de números enteros a de longitud n. Es necesario para cada posible subsegmento [l, r] (1 ≤ l ≤ r ≤ n) calcular el máximo común divisor (MCD) de los elementos de dicho subsegmento. Luego, entre todos los MCD obtenidos, encontrar la cantidad de valores distintos. Se requiere implementar un algoritmo eficiente, teniendo en cuenta que n puede ser de hasta 100000, y los elementos del arreglo, de hasta 10^9.

Formato de entrada

La primera línea contiene un número entero n (1 ≤ n ≤ 100000). La segunda línea contiene n números enteros a_i (1 ≤ a_i ≤ 10^9), separados por espacios.

Formato de salida

Imprima un número entero — la cantidad de valores distintos de MCD entre todos los subsegmentos del arreglo.

Ejemplos

Ejemplo 1

ENTRADA

3
6 10 15

SALIDA

6

Ejemplo 2

ENTRADA

4
2 4 8 16

SALIDA

4

Ejemplo 3

ENTRADA

5
7 14 21 28 35

SALIDA

5

Ejemplo 4

ENTRADA

5 10 15

SALIDA

3

main.go