أكبر قاسم مشترك لجميع المقاطع الفرعية

Go Hard math

مهمة «أكبر قاسم مشترك لجميع المقاطع الفرعية»

```html
<p>لدينا مصفوفة من الأعداد الصحيحة a بطول n. من الضروري لكل قطعة فرعية ممكنة [l, r] (1 ≤ l ≤ r ≤ n) حساب القاسم المشترك الأكبر (GCD) لعناصر هذه القطعة الفرعية. ثم من بين جميع القواسم المشتركة الكبرى التي تم الحصول عليها، إيجاد عدد القيم المختلفة. يجب تنفيذ خوارزمية فعالة، مع الأخذ في الاعتبار أن n يمكن أن تصل إلى 100000، وعناصر المصفوفة تصل إلى 10^9.</p>
```

تنسيق الإدخال

السطر الأول يحتوي على عدد صحيح واحد n (1 ≤ n ≤ 100000). السطر الثاني يحتوي على n من الأعداد الصحيحة a_i (1 ≤ a_i ≤ 10^9)، مفصولة بمسافات.

تنسيق الإخراج

أخرج عددًا صحيحًا واحدًا — عدد القيم المختلفة للقاسم المشترك الأكبر (GCD) بين جميع المقاطع الفرعية للمصفوفة.

أمثلة

مثال 1

الإدخال

3
6 10 15

الإخراج

6

مثال 2

الإدخال

4
2 4 8 16

الإخراج

4

مثال 3

الإدخال

5
7 14 21 28 35

الإخراج

5

مثال 4

الإدخال

5 10 15

الإخراج

3

main.go