Linear Congruential Generator
If you solved the task about Neumann's Random Generator you are already aware that not all methods of generating pseudo-random sequences are good. Particularly, Neumann's method is not suitable for anything except programming exercises.
Here is the other method which is more widespread (it is implemented in most of programming languages and libraries) and still simple enough: let us start with some initial number and generate each new member Xnext of a sequence by the current Xcur using the following rule:
Xnext = (A * Xcur + C) % M
So we need three constants to define such a sequence (and an initial number). Not all combinations of constants are good, however, here are many good variants which allow to produce sequences with period of M, i.e. significantly long.
In this task we are going to build this algorithm to tell the value of n-th member of a sequence.
Input data will contain the number of test-cases in the first line.
Then test-cases will follow, each in separate line.
Test-case consists of five values: A, C, M, X0, N where first three are the same as in formula, while X0 is the initial member of a sequence and N is the number of a member which we want to calculate.
Answer should contain N-th member's value for each test-case, separated by spaces.
Example:
input data:
2
3 7 12 1 2
2 3 15 8 10
answer:
1 11
Neumann's Random Generator只能用于练习编程，在实际中并没有什么用处，而今天介绍的这个方法，使用上还是很广泛的，而且非常简单。通过3个常数，1个起始值，再迭代N次就可以产生N个值的数列。
int main() {
std::ifstream infile("data.txt");
std::string line;
getline(infile, line);
int n;
std::stringstream ss(line);
ss >> n;
int res[n];
for (int i=0; i<n; i++) {
getline(infile, line);
std::stringstream ss(line);
int A, C, M, X0, N;
ss >> A;
ss >> C;
ss >> M;
ss >> X0;
ss >> N;
int Xnext;
int Xcur = X0;
for (int j=0; j < N; j++) {
Xnext = (A * Xcur + C) % M;
Xcur = Xnext;
}
std::cout << Xcur << " ";
}
std::cout << std::endl;
return 0;
}
往期精彩