โปรแกรม C++ หาค่าที่ไม่ซ้ำกันในลำดับ (Sequence) ที่กำหนด

ได้รับจำนวนเต็ม 4 ตัว: n, x, y, z สร้างลำดับ (sequence) โดย:

ตัวแรก: a₀ = x mod 2³¹
ตัวถัดไป: aᵢ = (aᵢ₋₁ × y + z) mod 2³¹ สำหรับ 1 ≤ i ≤ n-1

หาจำนวนค่าที่ไม่ซ้ำกัน (distinct) ในลำดับนี้

ตัวอย่าง

Input: n = 5, x = 1, y = 2, z = 1

Output: 5

คำอธิบาย: ลำดับ: 1, 3, 7, 15, 31 → ไม่ซ้ำทั้งหมด 5 ค่า

อัลกอริทึม

MOD = 2³¹ = 2147483648
สร้าง vector temp(MOD) ติดตามค่าที่เจอ
p = x % MOD, temp[p] = true, ans = 1
วน i = 1 ถึง n-1:
- p = (p * y + z) % MOD
- ถ้า temp[p] จริง → break (เจอซ้ำ)
- ans++, temp[p] = true
คืน ans

ตัวอย่างโค้ด C++

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

Input

5, 1, 2, 1