Größter gemeinsamer Teiler für alle Teilabschnitte

Go Hard math

Aufgabe «Größter gemeinsamer Teiler für alle Teilabschnitte»

Gegeben ist ein Array a ganzer Zahlen der Länge n. Für jeden möglichen Teilabschnitt [l, r] (1 ≤ l ≤ r ≤ n) muss der größte gemeinsame Teiler (GGT) der Elemente dieses Teilabschnitts berechnet werden. Anschließend soll unter allen berechneten GGTs die Anzahl der verschiedenen Werte ermittelt werden. Es ist ein effizienter Algorithmus zu implementieren, da n bis zu 100000 und die Array-Elemente bis zu 10^9 betragen können.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 100000). Die zweite Zeile enthält n ganze Zahlen a_i (1 ≤ a_i ≤ 10^9), getrennt durch Leerzeichen.

Ausgabeformat

Geben Sie eine ganze Zahl aus — die Anzahl der verschiedenen GGT-Werte unter allen Teilabschnitten des Arrays.

Beispiele

Beispiel 1

EINGABE

3
6 10 15

AUSGABE

6

Beispiel 2

EINGABE

4
2 4 8 16

AUSGABE

4

Beispiel 3

EINGABE

5
7 14 21 28 35

AUSGABE

5

Beispiel 4

EINGABE

5 10 15

AUSGABE

3

main.go