The next number
A generator stores a 48-bit number x. To output the next number it makes the step x ← (25214903917·x + 11) mod 248 and outputs the upper 32 bits of the new x, that is, ⌊x / 216⌋. This is how java.util.Random works: the low 16 bits of the state never come out.
You have seen two numbers the generator output in a row. Print the k numbers it will output next.
Input
The first line holds the number of generators T (1 ≤ T ≤ 10). Then T lines “o1 o2 k”: two consecutive numbers (0 ≤ o1, o2 < 232) and how many following ones are needed (1 ≤ k ≤ 20). It is guaranteed that the generator’s state is uniquely recovered from the two numbers.
Output
For each generator, a line of k numbers separated by spaces.
The first example is the same as in the article’s listing.
Examples
Example 1
1 3462021164 1173812125 5
525041693 1392299345 2581698045 466075430 711990521
Example 2
2 779501271 4044624960 3 4006504144 1178679997 4
2339400583 682989805 4045972280 3679756190 2684249300 754095740 2348544248
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
How many bits of the state are unknown once the first number is seen? How many variants does that give, and how do you check each one?
2The idea
The first number is the upper 32 bits of the state x1 after which it was output. Only the low 16 bits are unknown: 65,536 variants. For each, make one step of the generator and compare the upper 32 bits with the second number. A wrong variant matches by chance with probability about 2−32, so as a rule exactly one fits, and the statement guarantees it. Having found x1, simply run the generator onwards: it is deterministic, and everything it will output is known.
3Walkthrough
For each generator, try x from o1·216 to o1·216 + 216 − 1 until ⌊((25214903917·x + 11) mod 248) / 216⌋ equals o2. Then step to the second state and make k more steps, printing the upper 32 bits.
In Go the product does not fit in 64 bits, but that does not matter: multiplication modulo 264 and a mask for the low 48 bits give the same as multiplication modulo 248, because 248 divides 264.
3+Solution
4Complexity
At most 216 generator steps for each of the T generators plus k more: O(T·(216 + k)).
5Common mistakes
- Taking the low bits as zeros. Then the very first prediction diverges from the real one: an error in the low bits moves into the high ones after the multiplication.
- Starting from the wrong state. The found x1 produced the first number; the next k numbers come after the second, that is, from the third step.
- The wrong 32 bits. What comes out is the high bits, x / 216, not x mod 232; with the low ones no variant will match the second number.