ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Петрозаводск лето 2018. t.me/umnik_team Contest

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Алгебра на отрезке

Ограничение времени: 4.0 секунды
Ограничение памяти: 256 МБ
Дано простое число p.
Дальше всё происходит в мультипликативной группе по модулю p.
Дан массив длины n и q запросов двух типов:
  • l r x” — все числа на отрезке [l; r] умножить на x;
  • l r” — найти порядок подгруппы, порождённой элементами отрезка [l; r].

Исходные данные

В первой строке записаны 3 целых числа p, n, q — простой модуль, размер массива и количество запросов (2 ≤ p < 109, p — простое, 1 ≤ n ≤ 105, 1 ≤ q ≤ 105).
Во второй строке записан изначальный массив a длины n (1 ≤ ai < p).
В следующих q строках описаны запросы.
Запрос первого типа имеет вид “l r x” — все числа на отрезке [l; r] умножить на x (1 ≤ lrn, 1 ≤ x < p).
Запрос второго типа имеет вид “l r” — найти порядок подгруппы, порождённой элементами отрезка [l; r] (1 ≤ lrn).

Результат

На каждый запрос второго типа выведите ответ в отдельной строке.

Пример

исходные данныерезультат
17 3 7
10 16 2
2 2 3
2 1 2
2 2 2
1 1 2 3
2 1 1
2 3 3
2 1 3
8
16
2
4
8
16

Замечания

Оригинально в этой задаче был TL = 10 sec. Возможно, вам потребуются неасимптотические оптимизации для получения AC. Have fun :)
В этой секции будут даны определения всем понятиям из алгебры, которые встречаются в тексте условия. Все определения совпадают с обычными, поэтому если вы знакомы с основами алгебры, можно пропускать секцию.
Группа — множество, на котором определена ассоциативная бинарная операция. Группа замкнута относительно операции: для любых двух элементов a и b группы a ○ b также является элементом группы, где ○ - бинарная операция. В группе имеется нейтральный элемент (аналог 1 для умножения), и каждый элемент множества имеет обратный.
Мультипликативная группа по простому модулю p задаётся следующим образом. Элементы группы — ненулевые остатки по модулю p, т.е. 1, 2, …, p−1. Операция — умножение по модулю p. Легко видеть, что это действительно группа.
Подгруппа — подмножество H группы G, которое является группой относительно операции, определённой в G.
Подгруппа, порождённая множеством. Для произвольного подмножества SG, ⟨S⟩ обозначает наименьшую подгруппу G, содержащую S. Такая подгруппа определяется единственным образом.
Порядок группы — количество элементов группы.
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2124. Алгебра на отрезке