UVa 350

From Algorithmist
Jump to navigation Jump to search

350 - Pseudo-Random Numbers[edit]

Summary[edit]

For each set of values you are to determine the length of the cycle of pseudo-random numbers that will be generated.

Explanation[edit]

Given 4 values: Z, I, M, and L, you have to calculate the next pseudo-random number with L = (L * Z + I) % M and count the number of times a NEW L results.

Gotchas[edit]

If the repeated number is equal to the initial seed, increment the count.

Implementations[edit]

  • Use a counter for the case number.
  • Check for repeated values.

Optimizations[edit]

Use the Floyd's cycle finding algorithm.

Input[edit]

7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
2 0 786 0
9999 9999 9999 9998
0 0 0 0

Output[edit]

Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220
Case 5: 1
Case 6: 1