Задача №112117. Поломка Бамблби (C)
Входной файл: bumblebee.in, выходной файл: bumblebee.out
После очередного боя с десептиконами у Бамблби что-то сломалось. Теперь он делает непонятные вещи. Например, сейчас он пытается решить некоторую странную задачу. Опишем ее условие.
Введем две функции, определеные на множествах положительных натуральных чисел. Первой функцией будет mex ( a 1 , a 2 , ..., a n ) — наименьшее положительное натуральное число, которого нет среди чисел a 1 , a 2 , ..., a n . Второй функцией будет gcd ( a 1 , a 2 , ..., a n ) — наибольший общий делитель чисел a 1 , a 2 , ..., a n Бамблби сгенерировал массив натуральных чисел, а теперь хочет уметь делать следующую операцию: для произвольных чисел l и r перебирать все подмножества отрезка массива от a l до a r включительно, для каждого непустого подмножества считать его mex , а потом считать gcd всех получившихся mex -ов (несложно понять, что их может оказаться 2 r - l + 1 - 1 ).
К сожалению, вычислительная мощность Бамблби не позволяет ему решать эту задачу быстро. Помогите ему.
В первой строке входного файла дано число n ( 1 ≤ n ≤ 10 5 ) — длина массива, сгенерированного Бамблби.
Во второй строке дано n разделенных пробелами чисел a i ( 1 ≤ a i ≤ 10 9 ) — числа в массиве, сгенерированном Бамблби.
В третьей строке входного файла дано число q — количество запросов ( 1 ≤ q ≤ 10 4 ).
В каждой из следующих q строк входного файла записаны два числа l , r ( 1 ≤ l ≤ r ≤ n ) — отрезок, на котором надо посчитать значение функции.
В выходной файл выведите q строк — в i -ой строке выведите ответ на i -ый запрос.
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 4 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 1000 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
Третья группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех группах тестов, кроме последней, нажав на ссылку « Request feedback » на вкладке « Runs ».
4 1 2 3 4 2 1 1 1 4
2 1