НОД на отрезке чисел
Дано
n целых чисел. Необходимо ответить на q запросов, в каждом из которых требуется определить, каков наибольший общий делитель (НОД) всех чисел в диапазоне от l до r включительно.Входные данные
В первой строке входных данных указаны два числа
n (1 ≤ n ≤ 5000) и q (1 ≤ q ≤ 10).Во второй строке содержатся
n целых чисел, разделённых пробелами, которые составляют массив (1 ≤ ≤ ).Далее идут
q строк, каждая из которых задаёт пару чисел, определяющих соответствующий диапазон запроса (0 ≤ ≤ < n).Выходные данные
Программа должна вывести наибольший общий делитель всех чисел в отрезке с индексами от
l до r включительно.Примеры
Входные данные | Выходные данные |
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