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

Задача . F. Очередная задача про запросы к массиву


Задача

Темы: битмаски математика разделяй и властвуй Структуры данных теория чисел *2400

Вам дан массив \(a_1, a_2, \ldots, a_n\).

Необходимо выполнить \(q\) запросов следующих двух видов:

  1. «MULTIPLY l r x» — для каждого \(i\) (\(l \le i \le r\)) нужно умножить \(a_i\) на \(x\).
  2. «TOTIENT l r» — вычислить \(\varphi(\prod \limits_{i=l}^{r} a_i)\) по модулю \(10^9+7\), где \(\varphi\) обозначает функцию Эйлера.

Функцией Эйлера целого положительного числа \(n\) (обозначается как \(\varphi(n)\)) называется количество целых чисел \(x\) (\(1 \le x \le n\)), таких что \(\gcd(n,x) = 1\).

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

Первая строка содержит два целых числа \(n\) и \(q\) (\(1 \le n \le 4 \cdot 10^5\), \(1 \le q \le 2 \cdot 10^5\)) — количество элементов в массиве \(a\) и количество запросов.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 300\)) — элементы массива \(a\).

Следующие \(q\) строк задают запросы в формате, приведённом в условии.

  1. «MULTIPLY l r x» (\(1 \le l \le r \le n\), \(1 \le x \le 300\)) означает запрос умножения.
  2. «TOTIENT l r» (\(1 \le l \le r \le n\)) означает запрос вычисления функции Эйлера.

Гарантируется, что существует хотя бы один запрос типа «TOTIENT».

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

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

Примечание

В первом примере \(\varphi(1) = 1\) для первого запроса, \(\varphi(2) = 1\) для второго запроса и \(\varphi(6) = 2\) для третьего.


Примеры
№Входные данныеВыходные данные
1 4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4 
1
1
2

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

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

Ваш ответ

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


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

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