सभी उपखंडों के लिए महत्तम समापवर्तक

Go Hard math

कार्य «सभी उपखंडों के लिए महत्तम समापवर्तक»

पूर्णांकों की एक सरणी a दी गई है जिसकी लंबाई n है। प्रत्येक संभावित उप-खंड [l, r] (1 ≤ l ≤ r ≤ n) के लिए, इस उप-खंड के तत्वों का महत्तम समापवर्तक (GCD) निकालना आवश्यक है। फिर प्राप्त सभी GCD में से विभिन्न मानों की संख्या ज्ञात करनी है। एक कुशल एल्गोरिदम लागू करना आवश्यक है, यह ध्यान में रखते हुए कि n 100000 तक हो सकता है, और सरणी के तत्व 10^9 तक हो सकते हैं।

इनपुट प्रारूप

पहली पंक्ति में एक पूर्णांक 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