350 Pseudo-Random Numbers，循環長度

這題有點類似循環小數的做法，也是要紀錄它的餘數是否出現過，並且紀錄餘數的長度，有出現過，就將它在上一次出現長度相減後，便能算出它的循環長度。

首先可以先宣告兩個長度為10000的整數陣列(因為每個數最大不超過9999)：

int isTrue[10000] = {0}, len[10000];

而 isTrue 陣列是對應餘數使否有出現過，len 陣列是紀錄每個餘數的出現長度，則只須持續使用 (Z * L + I) % M 即可，一旦判斷出有出現過的餘數，即跳出迴圈，輸出長度：

int count = 0;
while (!isTrue[L])
{
    isTrue[L] = 1, len[L] = count ++;  
    L = PseRand(Z, I, M, L);  
}
printf("%d\n", count - len[L]);

(註：PseRand() 函式將四個數丟入後，運算 (Z * L + I) % M 後回傳 L 值)
By David.K

p350題目連結
回ACM題庫目錄
回首頁