Máximo divisor comum para todos os subsegmentos

Go Hard math

Tarefa «Máximo divisor comum para todos os subsegmentos»

Dado um array de inteiros a de comprimento n. É necessário para cada possível subsegmento [l, r] (1 ≤ l ≤ r ≤ n) calcular o máximo divisor comum (MDC) dos elementos desse subsegmento. Em seguida, entre todos os MDCs obtidos, encontrar a quantidade de valores distintos. É necessário implementar um algoritmo eficiente, considerando que n pode ser até 100000 e os elementos do array até 10^9.

Formato de Entrada

A primeira linha contém um número inteiro n (1 ≤ n ≤ 100000). A segunda linha contém n números inteiros a_i (1 ≤ a_i ≤ 10^9), separados por espaços.

Formato de Saída

Imprima um único número inteiro — a quantidade de valores distintos de MDC entre todos os subsegmentos do array.

Exemplos

Exemplo 1

ENTRADA

3
6 10 15

SAÍDA

6

Exemplo 2

ENTRADA

4
2 4 8 16

SAÍDA

4

Exemplo 3

ENTRADA

5
7 14 21 28 35

SAÍDA

5

Exemplo 4

ENTRADA

5 10 15

SAÍDA

3

main.go