#include <bits/stdc++.h>
using namespace std;

//*********************************
// HackerRank Prepare C++: BitArray
//*********************************

int main(void)
{
    vector<tuple<int, int, int, int, int>> testCases = {
        // input                                      expected
        // N                 S         P          Q   size
        {  3,                1,        1,         1,  3},
        {  10,       268435456,        3,         0,  2},
        {  100000000,923092883,976061291,1205350525,  100000000},
    };

    // 1 <= N <= 10^8
    // 0 <= S,P,Q < 2^31

    // output pseudo-code
    // ---------------------
    // a[0] = S (modulo 2^31)
    // for i = 1 to N-1
    //   a[i] = a[i-1]*P+Q (modulo 2^31)

    // Output Format:
    // A single integer that denotes the number of distinct integers
    // in the sequence "a"

    // https://en.wikipedia.org/wiki/Cycle_detection
    //
    // For any function f that maps a finite set S to itself, and any
    // initial value x0 in S,
    //
    // x0, x1 = f(x0), x2 = f(x1),....,xi = f(xi-1),..
    //
    // The sequences that are generated with the above formula can
    // either
    //     a. have unique values or
    //
    //     b. eventually must result in the use of the same value
    //     twice and once the value is repeated, the sequence must
    //     continue periodically.

    constexpr uint32_t TwoPow31 = 1U << 31;
    constexpr uint64_t TwoPow32 = 1UL << 32;
    
    bitset<32> bs31;
    bs31.set(31);
    bitset<64> bs32;
    bs32.set(32);
    cout << setw(15) << "TwoPow31: "      << TwoPow31                << endl
         << setw(15) << "TwoPow32: "      << TwoPow32                << endl
         << setw(15) << "bs31.to_ulong: " << bs31.to_ulong()         << endl
         << setw(15) << "bs32.to_ulong: " << bs32.to_ulong()         << endl
         << setw(15) << "INT_MAX: "       << INT_MAX                 << endl
         << setw(15) << "UINT_MAX: "      << UINT_MAX                << endl
         << setw(15) << "INT64_MAX: "     << INT64_MAX               << endl
         << setw(15) << "UINT64_MAX: "    << UINT64_MAX              << endl            
         << setw(15) << "pow(2,31): "     << (uint32_t) pow(2.0, 31) << endl << endl;

    for (auto test: testCases)
    {
        int N = get<0>(test);
        int S = get<1>(test);
        int P = get<2>(test);
        int Q = get<3>(test);

        vector<bool> boolBitset(TwoPow31);
        uint64_t a = S % TwoPow31;
        cout << "n: " << N << " i: " << 0 << " a: " << a << endl;
        boolBitset.at(a) = true;
        int i = 1;        
        for (; i <= N-1; i++)
        {
            // a[i] = a[i-1]*P+Q (modulo 2^31)
            a = (a * P + Q) % TwoPow31;
            if (i < 10)
                cout << "i: " << i << " a: " << a << endl;
            else if (i == 10 )
                cout << "calculating ...\n";
            if (boolBitset.at(a) == true)
                break;
            boolBitset.at(a) = true;
        }
        cout << endl;

        cout << "size: " << i << " expected: " << get<4>(test) << endl;
        cout << "----------------\n";
    }
    
    return 0;  
}