Задача Segtree2k17. В среде крутых олимпиадных гуру модно помнить наизусть решение такой задачи: Дан массив з N чисел и M запросов вида L R. На каждый такой запрос нужно вывести произведение элементов массива, имеющих индексы от L до R включительно. Так как произведение может быть весьма велико, ответ выводим по модулю Mod
Рассмотрим некую модификацию этой задачи. Условие менять не будем, изменим лишь ограничения:
Поскольку в этом случае входной файл будет достаточно большим, предлагается его генерировать. Код генератора (С++) должен быть встроен в решение. (Аналогичный код на языках Pascal и Python можно зарузить тут).
const int MAXN = 1000 * 1000;
long long a[MAXN];
long long mod;
unsigned s;
unsigned getNext(){
s ^= (s << 13);
s ^= (s >> 17);
s ^= (s << 5);
return s;
}
int main() {
unsigned n, m, seed ;
cin >> n >> m >> mod >> seed;
s = seed;
for(int i = 0; i < n; i++){
a[i] = getNext();
}
long long ans = 0;
for(int i = 0; i < m; i++){
unsigned left = getNext() % n;
unsigned right = getNext() % n;
if(left > right) swap(left, right);
long long result = query(left, right);
ans = (ans + result) % mod;
}
}
Таким образом, входными данными будут N, M, Mod, Seed, где Seed – начальное значение для генератора. В ответе нужно вывести сумму для каждого запроса (по модулю)
Технические условия. Программа Segtree2k17 (содержащая встроенный код генератора!) читает с устройства стандартного ввода натуральные числа N, M, Mod, Seed  seed<=232
Программа выводит на устройство стандартного вывода единственное число – сумму результатов (по модулю) на всех запросах.
Примеры
Ввод Вывод
10 15 1000000007 1 216091399
Ввод Вывод
5000 100000 1283189389247 8932 541836623127
Ввод Вывод
1000 100 100007 7632 47019
| 
