संख्याओं की एक श्रेणी पर GCD (महानतम समापवर्तक)
आपको दिए गए
n पूर्णांकों के आधार पर, आपको q प्रश्नों का उत्तर देना है। प्रत्येक प्रश्न में पूछा जाता है कि “इंडेक्स l से r तक (सभी संख्याओं को शामिल करते हुए) उन सभी संख्याओं का GCD (महानतम समापवर्तक) क्या होगा?”इनपुट
प्रथम पंक्ति में दो पूर्णांक
n (1 ≤ n ≤ 5000) और q (1 ≤ q ≤ 10) दिए जाते हैं।अगली पंक्ति में
n स्थान-प्रथक पूर्णांक हैं, जो ऐरे के तत्त्वों को दर्शाते हैं (1 ≤ ≤ )।उसके बाद आने वाली
q पंक्तियों में प्रत्येक पंक्ति दो संख्याओं की एक जोड़ी रखती है, जो प्रश्न के लिए परिभाषित श्रेणी (0 ≤ ≤ < n) को दिखाती है।आउटपुट
कार्यक्रम को इंडेक्स
l से r तक की सभी संख्याओं का GCD (महानतम समापवर्तक), समावेशी रूप से, प्रदर्शित करना चाहिए।उदाहरण
इनपुट | आउटपुट |
8 4
12 24 198 64 9 8 4 100
0 1
1 2
1 4
5 7 | 12 6 1 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB