Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Делители

(Время: 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, rn и 1 ≤ x ≤ 104.

Выходные данные

В выходной файл OUTPUT.TXT для каждого запроса на вывод количества делителей в отдельной строке выведите ответ по модулю 109+7.

Пример

INPUT.TXTOUTPUT.TXT
15
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 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023 7-8 классы
 2022 / 2023 9-11 классы
 2023 / 2024 7-8 классы
 2023 / 2024 9-11 классы
 2024 / 2025 7-8 классы
 2024 / 2025 9-11 классы
 A. Газировка
 B. Волшебная последовательность
 C. Сортировка массива
 D. Флаги
 E. Арифметическая прогрессия
 F. Делители

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru