Задача 10. Очень быстрая сортировка.
Ограничение по времени: 1.5 секунд
Ограничение по памяти: 512 мегабайт
Имеется рекуррентная последовательность A1, A2, …, AN, строящаяся по следующему правилу:
A1 = K
Ai+1 = (Ai ? M) % (232 – 1) % L
Требуется найти сумму всех нечетных по порядку элементов в отсортированной по неубыванию последовательности по модулю L.
Для входных данных
5 7 13 100
последовательность будет такой:
{7; 7 ? 13%100 = 91; 91 ? 13%100 = 83; 83 ? 13%100 = 79; 79 ? 13%100 = 27}, то есть {10; 91; 83; 79; 27}.
Отсортированная последовательность {7; 27; 79; 83; 91}.
Сумма элементов на нечетных местах = (7 + 79 + 91)%100 = 77.
Формат входных данных:
N K M L
5000000 ? N ? 60000000, 0 ? K, L, M ? 232 – 1
Формат выходных данных:
RESULT
Примеры:
Стандартный ввод Стандартный вывод
5 7 13 100 77
Замечание. Для представления элементов последовательности необходимо использовать тип данных unsigned int.
Для получения массива используйте цикл:
a[0] = K;
for (int i = 0; i < N-1; i++)
a[i+1] = (unsigned int) ((a[i]*unsigned long long)M)&0xFFFFFFFFU)%L;
Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!
Елена
КГСХА
Спасибо большое за выполненную работу! Были постоянно на связи. Задания готовы раньше сро...
Елена
СИБИТ
Вероника, огромное спасибо за оперативность и отличную работу, оценили 100%, РЕКОМЕНДУЮ
Вероника
Московская Международная Академия
Очень быстро выполнила заказ. За что большое спасибо, отдельно знает свою работу.
Максим
ТУСУР
Данный исполнитель выполнил ту работу от которой многие отказывались или не справлялись.