images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
27/04/2024 01:06:56

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1609. Aladin

Ограничения: время – 8s/16s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Aladin was walking down the path one day when he found the strangest thing. `N` empty boxes right next to a weird alien machine. After a bit of fumbling around he got the machine to do something. The machine now accepts 4 integers `L`, `R`, `A` and `B`. After that hitting the big red glowing button labeled "NE DIRAJ" causes the machine to go crazy and follow the next routine:
  • Set the number of stones in the box labeled `L` to `A` modulo `B`.
  • It procedes to fly to the box labeled `L+1`, and set the number of stones there to `(2*A)\ mod\ B`.
  • It procedes to fly to the box labeled `L+2`, and set the number of stones there to `(3*A)\ mod\ B`.
  • Generaly, it visits each box labeled between `L` and `R`, and set the number of stones there to `((X\ -\ L\ +\ 1)*A)\ mod\ B`, where `X` is the box label.
  • After it visits the box labeled `R`. It settles down for further instructions.
During the game Aladin wonders what is the total number of stones in some range of boxes.
Write a program that simulates the device and answers Aladins questions.
Input
The first line contains two integers `N` and `Q` (`1\ ≤\ N\ ≤\ 1\ 000\ 000\ 000`, `1\ ≤\ Q\ ≤\ 50\ 000`), number of boxes and number of queries.
The next `Q` lines contain information about the simulation.
If the line starts with 1, than it follows the format "1 `L\ R\ A\ B`" (`1\ ≤\ L\ ≤\ R\ ≤\ N`, `1\ ≤\ A,\ B\ ≤\ 1\ 000\ 000`), meaning that Aladin keyed in numbers `L`, `R`, `A` and `B` in the device and allowed the device to do its job.
If the line starts with 2, than it follows the format "2 `L\ R`" (`1\ ≤\ L\ ≤\ R\ ≤\ N`). Meaning that Aladin wonders how many stones in total are their stones are in boxes labeled `L` to `R` (inclusive).
Output
For each query beginning with 2 output the answer to that particular query. Queries should be processed in the order they are given in the input.

Sample Input 1

6 3
2 1 6
1 1 5 1 2
2 1 6

Sample Output 1

0
3

Sample Input 2

4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4

Sample Output 2

3
2
1
0

Sample Input 3

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

Sample Output 3

16
0
First sample description:
The boxes start containing {0, 0, 0, 0, 0, 0}, 0 stones in total.
After that the device sets the stones to {1 mod 2, 2 mod 2, 3 mod 2, 4 mod 2, 5 mod 2, 0} = {1,0,1,0,1,0}, or 3 stones in total.
Source: COCI 2009/2010 contest #1
loading