Tìm số phần tử phân biệt trong dãy số sinh ngẫu nhiên (C++17)

Cho n, x, y, z. Sinh dãy: a[0] = x mod 2³¹, a[i] = (a[i-1]*y + z) mod 2³¹. Đếm số giá trị phân biệt trong n phần tử đầu.

Ví dụ

Đầu vào: n=5, x=1, y=2, z=1

Đầu ra: 5

Giải thích: Dãy: 1, 3, 7, 15, 31 → 5 giá trị khác nhau.

Phương pháp: Mảng boolean đánh dấu (với MOD = 2³¹)

• Khởi tạo vector seen(MOD) (MOD = 2147483648).
• Tính lần lượt, nếu gặp giá trị đã thấy → dừng (chu kỳ).
• Đếm số giá trị mới.

Lưu ý: MOD = 2³¹ rất lớn (2 tỷ), vector nén bit vẫn cần ~256MB. Giải pháp thực tế dùng unordered_set hoặc Floyd cycle detection.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 2147483648LL;

int solve(int n, long long x, long long y, long long z) {
    unordered_set seen;
    long long p = x % MOD;
    seen.insert(p);
    int ans = 1;
    for (int i=1; i

Đầu ra chương trình
5