JDCC '15 Contest 2 P5 - Randomize

View as PDF

Submit solution

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

Author:
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:

\[f(0) = SEED\]

\[ 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

2
3 2 5
4 5 3

Sample Output

3.400000
3.000000

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\).


Comments

There are no comments at the moment.