Linear Congruential Generator

Problem #25

Tags: arithmetic modulo practical random

Who solved this?

Back to English version

Если вы уже решали задачу про Генератор случайных чисел фон-Нейманна то уже знаете, что не все методы генерации псевдослучайных последовательностей хороши. В частности Нейманновский метод годится разве что для упражнений в программировании :)

Вот другой способ, гораздо более распространённый (он реализован в большинстве стандартных библиотек и языков программирования) и в то же время весьма прост: начнем с некоторого начального числа, и будем получать каждое следующее значение последовательности (Xnext) на основании текущего (Xcur) по следующему правилу:

Xnext = (A * Xcur + C) % M

Нам понадобятся три константы чтобы однозначно задать последовательность (и начальное значение). Не все сочетания констант хороши (подробности можно прочесть в Random Numbers), однако всё-таки существует большое количество хороших вариантов, которые позволяют получать последовательности с периодом M, т.е. весьма длинные.

В этом упражнении мы собираемся запрограммировать такой алгоритм чтобы узнать N-ый член последовательности.

Входные данные содержат количество тест-кейсов в первой строке.
Дальше следуют сами тест-кейсы, по одному в каждой строке - они состоят из пяти значений: A, C, M, X0, N, где первые три - константы из формулы, X0 - это начальный член - а N порядковый номер члена который требуется вычислить.
Ответы должны содержать требуемые члены случайных последовательностей для каждого теста, через пробел.

Пример:

входные данные:
2
3 7 12 1 2
2 3 15 8 10

ответ:
1 11
You need to login to get test data and submit solution.