ITSA_38_Pro5

[Problem 5] Pseudo Random Generation

成績: 0 / 倒扣: 0.8

Problem Description
Random numbers are usually used in computer program. Computer can't produce pure random numbers but can produce pseudo random numbers. There are some pseudo random generators in our program language library which are usually used.
There is a method which is usually used to produce pseudo random numbers. The method is called linear congruential method. This method needs 4 parameters:

m  a  c  X0

a modulus  a multiplier  a addend  a initial number(seed number)

m > 0 0 < a < m0 ≤ c < m 0 ≤ X0 < m

The pseudo random numbers are produced by follow program states: 
X_n+1 = ( aX_n + c ) mod m 
For example, if a = 7, c = 5, m =12, and X₀ = 4 then the program produces a series of the pseudo random numbers as follow:

Xn	aXn + c	Xn+ 1 = ( aXn + c ) mod m
4  9 8 1 0 5	33  68  61 12  5  40	9  8  1  0  5  4

In this case, the cycle length of a pseudo random numbers sequence is 6. In other words, the program produces six different pseudo random numbers and the series of the pseudo random numbers will repeat. Theoretically, the cycle length cannot exceed m hat is produced by the method (because mod m).

In this problem, you are given a, c, m, and X₀ and asked to computer the cycle length. Note that, the repetition is not necessarily from the first seed. For example, if the pseudo random number sequence is {3, 7, 2, 10, 17, 8, 2, 10, 17, 8, ...} then the cycle length is 4.


Input File Format
In the first line, there is a integer n indicating how many cases. Followed the first line, there are four integers separated by a space in each line. The four integers indicate the numbers of a, c, m and X₀ in this order.


Output Format
Output the cycle length of every case line by line.
Example

Sample Input:	Sample Output:
2  2179 1839 3279 1511  3561 5353 6219 1234	546  345

-----------------------------------------------------------------------------------------------------------




※使用 hashMap不重複計數的特性






import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {


 public static void main(String[] args) {

  Scanner sc=  new Scanner(System.in);

  int count = 0;

  count  = Integer.parseInt(sc.nextLine().trim());

  while(count-->0)
  {
   int a = sc.nextInt();
 
   int c = sc.nextInt();
 
   int m = sc.nextInt();
 
   int x = sc.nextInt();
 
   int counter = 0,ans = 0;
 
   HashMap<Integer,Integer>  hm = new HashMap<Integer,Integer>();
 
   while(counter<m)
   {
    counter++;
  
    x = (a * x + c) % m ;
  
    if(!hm.containsKey(x))
     hm.put(x, 1);
    else
    {
     int temp = hm.get(x);
     temp++;
     hm.put(x, temp);
    }
   }


//foreach
   for(Map.Entry map:hm.entrySet())
   {
    if(!hm.containsValue(1))
     ans++;
   }
    System.out.println(ans);
  }
  sc.close();
 }
}