c085 - 00350 - Pseudo-Random Numbers

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定虛擬亂數產生公式 (Z*L+I) mod M 的 cycle length。輸入包含 Z, I, M, L 四個整數，其中 L 是 seed。輸出每個測試案例的 cycle length，從 Case 1 開始編號。輸入以四個 0 結尾表示結束。

解題思路

這題的核心是模擬虛擬亂數的產生過程，並找出 cycle 的長度。程式使用一個 chat 陣列來記錄每個亂數出現的次數。每次產生新的亂數時，將其在 chat 陣列中的計數器加 1。當某個亂數再次出現時（chat[d] == 2），表示找到了 cycle。cycle length 就是找到重複亂數之前產生的亂數個數。

複雜度分析

• 時間複雜度: O(M)。在最壞的情況下，需要產生 M 個亂數才能找到 cycle。
• 空間複雜度: O(M)。需要一個大小為 M 的 chat 陣列來記錄每個亂數的出現次數。

程式碼

#include <iostream>
using namespace std;
int main(){
	int chat[10001]={0};
	int a,b,c,d,i=1;
	while(cin >> a >> b >> c >> d){
		if(a==0&&b==0&&c==0&&d==0)
			break;
		for(int i=0;i<10001;i++)
			chat[i]=0;	
		int ans=0;
		while(chat[d]!=2){
			d=(a*d+b)%c;
			chat[d]++;
			ans++;
		}	
		cout << "Case " << i << ": " << ans-1 << "\n";
		i++;
	}
}