[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:
The pseudo random numbers are produced by follow program states:
Xn+1 = ( aXn + c ) mod m
For example, if a = 7, c = 5, m =12, and X0 = 4 then the program produces a series of the pseudo random numbers as follow:
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 X0 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 X0 in this order.
Output Format
Output the cycle length of every case line by line.
Example
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 |
Xn+1 = ( aXn + c ) mod m
For example, if a = 7, c = 5, m =12, and X0 = 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 problem, you are given a, c, m, and X0 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 X0 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 |
題意 : 給你亂數的seed 尋找第一次出現重複數字x和第一次出現x中間隔了幾個數
做法 : 我先設一個array-> test[]並預設為0 當test[x]為0代表x是第一次出現 設test[x] = sum,記錄她出現的位置 , 因此若test[x]!=0則代表找到第一個cycle(重複的數),並輸出 sum-test[x](他們之間差幾個數)
沒有留言:
張貼留言
注意：只有此網誌的成員可以留言。