JDCC '15 Contest 2 P5 - Randomize

View as PDF

Submit solution

Points: 15
Time limit: 5.0s
Memory limit: 256M

Problem types

For her new ICS assignment, Caroline needs to design a program that uses random numbers. However, she discovers that Ms. Dyke has forbidden using any built-in functions! Now, she needs to create a random number generator to make her assignment work. After checking online, she finds that random numbers can be generated using the following function:

\displaystyle f(0) = SEED

\displaystyle  F(N) =  (A \times F(N-1) + B) \bmod P

Where SEED is some initial value between 0 and P-1 inclusive. After some tinkering she finds that for most values of A, B, and P, the generated numbers quickly fall into a repeating cycle. She’d like to figure out which values of A, B, and P produce the best results and has enlisted your help to find the average length of a cycle for one set of values.

Note: The cycle length for some value of SEED is defined as smallest value N for which F(N) produces a number already in the sequence. For example, if SEED = 1, F(1) = 2, F(2) = 3, and F(3) = 3, then the cycle length is 3, as 3 was already in the sequence. The average length of a cycle is defined as the average of the cycle lengths for every possible value of SEED.

Input Specification

The first line of the input provides the number of test cases, T\ (1 \le T \le 100). T test cases follow. Each test case contains 3 integers, A, B, and P\ (1 \le A, B, P \le 10^6).

For the first 20\% of cases, A, B, P \le 10^3.

Output Specification

For each test case, your program should output one real number, rounded to 6 decimal places, the average length of a cycle.

Sample Input

3 2 5
4 5 3

Sample Output


Explanation for Sample

In the second test case, if you start with a SEED of 0, then

  • F(1) = 4(0) + 5 \bmod 3 = 2
  • F(2) = 4(2) + 5 \bmod 3 = 1
  • F(3) = 4(1) + 5 \bmod 3 = 0

Since 0 is already in the sequence, the cycle length is 3. Starting with 1 or 2 will also result in a cycle length of 3, so the average cycle length is 3.


There are no comments at the moment.