C++ প্রোগ্রাম: একটি দেওয়া সিকোয়েন্সে ভিন্ন উপাদান বের করা

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

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

ইউনিক ভ্যালুগুলো হল {1, 3, 7, 15, 31}। তাই, উত্তর ৫।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:-

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