Linear congruential generator
We have designed and implemented a new prime factorization algorithm. It is believed that the most challenging inputs to the algorithm are integers which are the product of K distinct primes. We would like to test the algorithm on a sequence of integers generated by a linear congruential generator. The question is how to choose the generator seed so that many challenging inputs are generated.
You are given parameters of a linear congruential generator. Your task is to compute the seed of the generator which will produce a sequence of N pseudorandom values containing as many as possible integers whose prime factorization consists of exactly K distinct primes.
The input is one line containing integers A, C, M, K, N separated by a space. Values A, C, M determine linear congruential generator given by formula
xi+1=Axi+C mod M.
It is guaranteed that the generator has a period of length M. Value N is the number of inputs we are supposed to generate from
a chosen seed to test the algorithm. The generated values are thus x1, x2,...,xN where x1 equals the seed.
Values of A, C and M are not greater than 3 × 108. Moreover, 1 ≤ K ≤ 10 and 1 ≤ N ≤ M.
The output is one line containing two integers S and I separated by a space. S is the optimal seed, I is the number of the most challenging inputs that will be generated from S. If more seeds generate the same number of the most challenging inputs, S is that seed among them which is generated by the generator from the initial value x1=0 earlier than the other seeds.
5 11 8 1 4Output
0 3The generator produces numbers 0, 3, 2, 5, 4, 7, 6, 1. Since K=1, the most challenging inputs are primes. If seed 0 is chosen, primes 2, 3 and 5 are included in the generated sequence of length N=4. This is the optimal setting as a sequence of length 4 cannot include all 4 primes produced by the generator.
5 3 16 2 7Output
8 3The produced numbers are sequentially 0, 3, 2, 13, 4, 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9. Since K=2, the most challenging inputs are those numbers in 0,..,15 that are products of two distinct primes (6, 10, 14, 15). The optimal seed is thus 8.
17 9 32 2 10Output
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set