Chương trình C ++ để tìm ra các phần tử riêng biệt trong một chuỗi nhất định

Giả sử chúng ta được cung cấp ba số nguyên n, x, y và z. Chúng ta phải tạo một chuỗi từ các số nguyên đã cho, trong đó mục đầu tiên của chuỗi là (x modulo 2 ³¹ ). Ngoài phần tử đầu tiên, các phần tử khác trong chuỗi a _i =(a _(i-1) * y + z) modulo 2 ³¹ , trong đó 1 ≤ i ≤ n - 1. Chúng ta phải tìm ra số lượng các số nguyên khác nhau trong dãy chúng ta đã thực hiện.

Vì vậy, nếu đầu vào là n =5, x =1, y =2, z =1, thì đầu ra sẽ là 5.

Các giá trị duy nhất là {1, 3, 7, 15, 31}. Vì vậy, câu trả lời là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MOD:=2 ^ 31
• Xác định tạm thời mảng
• thay đổi kích thước tạm thời của mảng thành giá trị của MOD
• p:=x mod MOD
• temp [p]:=true
• ans:=1
• để khởi tạo i:=1, khi i
• p:=((p * y) + z) mod MOD
• nếu temp [p] là true, thì -
  • Ra khỏi vòng lặp
• tăng ans lên 1
• temp [p]:=true

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

5, 1, 2, 1

Đầu ra

5