Олимпиадный тренинг

Задача . F. SUM и REPLACE


Задача

Темы: Перебор снм Структуры данных теория чисел *2000

Обозначим за D(x) количество положительных делителей натурального числа x. К примеру, D(2) = 2 (2 делится на 1 и 2), D(6) = 4 (6 делится на 1, 2, 3 и 6).

Вам дан массив a из n целых чисел. Нужно обрабатывать два вида запросов:

  1. REPLACE l r — для каждого заменить ai на D(ai);
  2. SUM l r — посчитать .

Выведите ответ на каждый запрос SUM.

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

В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3·105) — количество элементов в массиве и количество запросов, соответственно.

Во второй строке заданы n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — элементы массива.

Затем следуют m строк, в каждой из которых записаны 3 целых числа ti, li, ri, обозначающих i-й запрос. Если ti = 1, то i-й запрос — REPLACE li ri, иначе это запрос SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n).

Хотя бы один запрос имеет тип SUM.

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

Для каждого запроса SUM выведите ответ на него.


Примеры
№Входные данныеВыходные данные
1 7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7 
30
13
4
22

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет