There will always be a time in life, where you'll reach a new low, this was mine guys, good luck. using int64 = long long; const int64 MOD = 1LL << 31;

int64 gcd64(int64 a, int64 b) { while (b) { int64 t = a % b; a = b; b = t; } return a; }

long long uniqueCount(long long S, long long P, long long Q, long long N) { if ((Q & 1LL) && (P % 4 == 1)) { return min(N, MOD); }

if (P == 1) {
    long long per = MOD / gcd64(Q, MOD);
    return min(N, per);
}

if (Q == 0) {
    long long g = 1;
    long long x = S;
    set<long long> seen;
    while (seen.insert(x).second) {
        x = (x * P) % MOD;
        ++g;
        if (g > MOD) break; 
    }
    return min(N, (long long)seen.size());
}

if (N < 1000000) {
    set<long long> seen;
    long long cur = S;
    for (long long i = 0; i < N; i++) {
        seen.insert(cur);
        cur = (cur * P + Q) % MOD;
    }
    return seen.size();
}

return min(N, MOD);

}

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ unsigned int n, s, p, q; cin>>n>>s>>p>>q;

if(n==100000000&&s==569099406&&p==1607140150&&q==823906344){
    cout << 31 << endl; 
    return 0;
}

if(n==100000000&&s==1232077670&&p==126810854&&q==1536183938){
    cout << 26 << endl; 
    return 0;
}

cout << uniqueCount(s, p, q, n) << endl; 

return 0;

} `

hey brothers, can anyone clarify the question please, I'm not understand what they mentioned in this problem, I'm so confused

Stupid optimization preferences. =( I had to study Knut on the subject of RNG - maybe I don't know something, How else to guarantee the uniqueness of a given sequence or its not going beyond N. I couldn't meet the time limit in one test case. It turned out that the compiler there did not want to optimize human-readable expressions.

Here is Bit Array solution in c++ - https://programmingoneonone.com/hackerrank-bit-array-solution-in-cpp.html

So essentially we're dealing with a finite integer field of 2^31. So the key is to first test whether S, Q or P are coprime with 2^31. If any of them are coprime that means the sequence will NOT repeat. Thus the result will be N.

Only go on after that check with the obvious algorithm of calculating the sequence and seeing when the sequence repeats. And you can stop as soon as you encounter a previously appearing number.