НОД на отрезках
(Время: 1 сек. Память: 32 Мб Сложность: 46%)
Задан числовой массив A[1..N]. Необходимо выполнить M операций вычисления наибольшего общего делителя среди всех чисел отрезка A[L..R].
Входные данные
Первая строка входного файла INPUT.TXT содержит число N – размер массива (N ≤ 105). Во второй строке записаны N чисел – элементы массива (целые числа от 1 до 109). Третья строка содержит натуральное число M – количество запросов вычисления НОД (M ≤ 30 000). Следующие M строк содержат пары чисел L и R (1 ≤ L ≤ R ≤ N), описывающие отрезки.
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса выведите значение НОД на отрезке через пробел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
2 2 2 1 5
2
2 3
2 5 | 2 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
