मान लीजिए हमें तीन पूर्णांक संख्याएँ n, x, y और z दी गई हैं। हमें दिए गए पूर्णांकों से एक अनुक्रम बनाना है जहां अनुक्रम का पहला आइटम है (x modulo 2 31 ) पहले तत्व के अलावा, अनुक्रम में अन्य तत्व ai =(ए<उप>(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 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- रक्षा मंत्रालय:=2^31
- एक सरणी अस्थायी परिभाषित करें
- मॉड के मान के लिए अस्थायी सरणी का आकार बदलें
- p :=x मॉड एमओडी
- अस्थायी[p] :=सच
- उत्तर:=1
- इनिशियलाइज़ i :=1 के लिए, जब i
- p :=((p * y) + z) मॉड मॉड
- यदि अस्थायी[p] सत्य है, तो −
- लूप से बाहर आएं
- उत्तरों को 1 से बढ़ाएँ
- अस्थायी[p] :=सच
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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
