मान लीजिए हमें तीन पूर्णांक n, x, y, और z दिए गए हैं। हमें दिए गए पूर्णांकों से एक अनुक्रम बनाना है जहां अनुक्रम का पहला आइटम (x मॉड्यूलो 2^31) है। पहले तत्व के अलावा, अनुक्रम में अन्य तत्व a_i = (a_(i-1) * y + z) मॉड्यूलो 2^31 हैं, जहां 1 ≤ i ≤ n - 1। हमें बनाए गए अनुक्रम में विशिष्ट पूर्णांकों की संख्या ढूंढनी है।
तो, यदि इनपुट n = 5, x = 1, y = 2, z = 1 है, तो आउटपुट 5 होगा।
अद्वितीय मान हैं {1, 3, 7, 15, 31}। तो, उत्तर 5 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- MOD := 2^31
- एक सरणी temp परिभाषित करें
- सरणी temp का आकार MOD के मान पर बदलें
- p := x mod MOD
- temp[p] := true
- ans := 1
- i := 1 से प्रारंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें:
- p := ((p * y) + z) mod MOD
- यदि temp[p] सत्य है, तो:
- लूप से बाहर आएं
- ans को 1 से बढ़ाएं
- temp[p] := true
- ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 2147483648;
int solve(int n, long long x, long long y, long long z) {
vector<bool> temp;
temp.resize(MOD);
long long p = x % MOD;
temp[p] = true;
int ans = 1;
for (int i = 1; i < n; ++i) {
p = ((p * y) + z) % MOD;
if (temp[p])
break;
++ans;
temp[p] = true;
}
return ans;
}
int main() {
cout << solve(5, 1, 2, 1) << endl;
return 0;
}
इनपुट
5, 1, 2, 1
आउटपुट
5
