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.