
ZOJ Problem Set  1278
Computers normally cannot generate really random numbers, but frequently are used to generate sequences of pseudorandom numbers. These are generated by some algorithm, but appear for all practical purposes to be really random. Random numbers are used in many applications, including simulation. A common pseudorandom number generation technique is called the linear congruential method. If the last pseudorandom number generated was L, then the next number is generated by evaluating ( Z x L + I ) mod M, where Z is a constant multiplier, I is a constant increment, and M is a constant modulus. For example, suppose Z is 7, I is 5, and M is 12. If the first random number (usually called the seed) is 4, then we can determine the next few pseudorandom numbers are follows: As you can see, the sequence of pseudorandom numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus, M. In this problem you will be given sets of values for Z, I, M, and the seed, L. Each of these will have no more than four digits. For each such set of values you are to determine the length of the cycle of pseudorandom numbers that will be generated. But be careful: the cycle might not begin with the seed!
7 5 12 4 Sample Output Case 1: 6 Source: North Central North America 1996 