Задача по алгоритмам и структурам данных

C#

Ограничение по времени: 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;

Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!