高中生程式解題:c085: 00350 - Pseudo-Random Numbers－資工趴趴熊的小天地

Content

電腦無法產生真正的亂數（Random numbers），但是經由某些程序電腦可以產生虛擬亂數（pseudo-random numbers）。亂數被使用在很多應用上，像是模擬等。

有一種常用的虛擬亂數產生方法：如果上一個亂數是L，那下一個亂數產生的方法是
(Z*L+I) mod M，在這裡Z、I、M都是常數。例如：假設Z=7 I=5 M=12。如果第一個亂數（通常叫做 seed）是 4 , 那我們可以產生以下幾個虛擬亂數:

我們可以發現，經過6個數字後，虛擬亂數的序列重複了，也就是說cycle length=6。
在這個問題中，你將會被給Z、I、M還有L（就是seed）的值（全部不大於9999）,對每一組Z、I、M、L，要請你輸出所產生的虛擬亂數的cycle length。
請注意：cycle並不一定從seed開始。

Input

輸入的每一行有4個整數,依序為Z, I, M, L。（L一定比M小）
輸入的最後一行為4個0，代表輸入結束。

Output

對每一行輸入，輸出這是第幾組測試資料（連續數字，從1開始）和所產生的虛擬亂數的cycle length。

Sample Input #1

7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
0 0 0 0

Sample Output #1

Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 1.0s , <1K

#include <iostream>
using namespace std;
  
int main() {
    int Z, I, M, L, Case = 1;
    while (cin >> Z >> I >> M >> L) {
        if (Z + I + M + L == 0) break;
        int arr[M]; //因為 %M，所以我只要開M個位置就好 
        for (int i = 0; i < M; i++) {
            arr[i] = -1; 
        }
        //依照範例:arr[12]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
        
        int rank = 0;//計算現在是亂數出線的第幾個數 
        while (arr[L]==-1) {//如果還沒重複，arr[l]會為-1，進去迴圈，若重複了(arr[l]就不會為-1)，跳出迴圈 
            arr[L] = rank;
            L = (Z * L + I) % M;//找出新的亂數 
            rank++;
        //所以第一個迴圈跑完後  arr[12]={-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1}
        //所以第二個迴圈跑完後  arr[12]={-1,-1,-1,-1,0,-1,-1,-1,-1, 1,-1,-1}
        //所以第三個迴圈跑完後  arr[12]={-1,-1,-1,-1,0,-1,-1,-1, 2, 1,-1,-1}
        //所以第四個迴圈跑完後  arr[12]={-1, 3,-1,-1,0,-1,-1,-1, 2, 1,-1,-1}
        //所以第五個迴圈跑完後  arr[12]={ 4, 3,-1,-1,0,-1,-1,-1, 2, 1,-1,-1}
        //.
		//.
		//.
        }
        cout << "Case " << Case << ": " << rank - arr[L] << "\n";
        Case++;
    }
    return 0;
}
/*
這裡解釋下
若亂數循環為498105105105....  cycle length為3 
亂數循環出現依序: 4 9 8 1 0 5 1(重複!) 0 5
則rank排序為:     0 1 2 3 4 5 6        7 8
所以 cycle length = 6-3=3 
*/