Делители
(Время: 5 сек. Память: 512 Мб Сложность: 69%)
Задан массив a[1..n], состоящий из n натуральных чисел. Требуется выполнить над массивом ряд операций двух типов:
- 0 i x – присвоить i-му элементу массива значение x;
- 1 l r – вывести количество делителей у произведения чисел на отрезке с l по r. Это число может быть довольно большим, поэтому ответ требуется вывести по модулю 109+7.
Входные данные
В первой строке входного файла INPUT.TXT содержится число n (1 ≤ n ≤ 5×104) – количество элементов массива.
Во второй строке записаны n чисел ai (1 ≤ ai ≤ 104) – элементы массива.
В третьей строке дано число q (1 ≤ q ≤ 104) – количество запросов.
В каждой из следующих q строк записано по три числа. Если первое из этих чисел равно 0, то это запрос обновления элемента массива, если же первое число равно 1, то это запрос на нахождение количества делителей у произведения чисел на отрезке [l, r] по модулю 109+7.
Гарантируется, что во всех запросах 1 ≤ i, l, r ≤ n и 1 ≤ x ≤ 104.
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса на вывод количества делителей в отдельной строке выведите ответ по модулю 109+7.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5
2 3 4 5 6
6
1 2 4
1 2 3
0 1 1
0 4 7
1 1 3
1 1 4
| 12 6 6 12 |
Система оценки
Решения, работающие только для n ≤ 10, ai ≤ 30 и q ≤ 20, будут оцениваться в 30 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|