Plus grand commun diviseur pour tous les sous-segments

Go Hard math

Tâche «Plus grand commun diviseur pour tous les sous-segments»

Étant donné un tableau d’entiers a de longueur n. Pour chaque sous-segment possible [l, r] (1 ≤ l ≤ r ≤ n), il faut calculer le plus grand commun diviseur (PGCD) des éléments de ce sous-segment. Ensuite, parmi tous les PGCD obtenus, trouver le nombre de valeurs distinctes. Il est nécessaire d’implémenter un algorithme efficace, sachant que n peut aller jusqu’à 100000 et les éléments du tableau jusqu’à 10^9.

Format d\ entrée

La première ligne contient un entier n (1 ≤ n ≤ 100000). La deuxième ligne contient n entiers a_i (1 ≤ a_i ≤ 10^9), séparés par des espaces.

Format de sortie

Affichez un seul entier — le nombre de valeurs distinctes du PGCD parmi tous les sous-segments du tableau.

Exemples

Exemple 1

ENTRÉE

3
6 10 15

SORTIE

6

Exemple 2

ENTRÉE

4
2 4 8 16

SORTIE

4

Exemple 3

ENTRÉE

5
7 14 21 28 35

SORTIE

5

Exemple 4

ENTRÉE

5 10 15

SORTIE

3

main.go