একটি প্রদত্ত অনুক্রমের স্বতন্ত্র উপাদানগুলি খুঁজে বের করার জন্য C++ প্রোগ্রাম

ধরুন আমাদের তিনটি পূর্ণসংখ্যা দেওয়া হল n, x, y, এবং z। আমাদের প্রদত্ত পূর্ণসংখ্যা থেকে একটি ক্রম তৈরি করতে হবে যেখানে ক্রমটির প্রথম আইটেমটি (x modulo 2³¹ ) প্রথম উপাদান ব্যতীত, a_i অনুক্রমের অন্যান্য উপাদান =(a_(i-1) * y + z) মডিউল 2³¹ , যেখানে 1 ≤ i ≤ n - 1। আমাদের তৈরি করা ক্রমটিতে আমাদের স্বতন্ত্র পূর্ণসংখ্যার সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় n =5, x =1, y =2, z =1, তাহলে আউটপুট হবে 5।

অনন্য মান হল {1, 3, 7, 15, 31}। সুতরাং, উত্তর হল 5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

MOD :=2^31
একটি অ্যারে টেম্প সংজ্ঞায়িত করুন
অ্যারে টেম্পকে MOD-এর মান পরিবর্তন করুন
p :=x mod MOD
temp[p] :=সত্য
উত্তর :=1
আরম্ভ করার জন্য i :=1, যখন i করুন
p :=((p * y) + z) মোড MOD
যদি temp[p] সত্য হয়, তাহলে −
- লুপ থেকে বেরিয়ে আসুন
উত্তর 1 দ্বারা বৃদ্ধি করুন
temp[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