The number of distinct integers in the created sequence

bitarray.cpp

//
//  a[0] = S (modulo 2^31)
//  for i = 1 to N-1
//      a[i] = a[i-1]*P+Q (modulo 2^31) 
//
// https://www.hackerrank.com/challenges/bitset-1/forum/comments/138875

#include <algorithm>
#include <iostream>

constexpr unsigned exponent = 31;
constexpr unsigned two_to_exponent = 1u << exponent;

unsigned solve_p_even( unsigned n, unsigned s, unsigned p, unsigned q ) {

    if( p == 0 ) {
        if( s == q )
            return 1;
        return 2;
    }

    if( s == 0 && q == 0 )
        return 1;

    unsigned a1_minus_a0 = ( p - 1 ) * s + q;
    unsigned numerator =
        exponent - __builtin_popcount( ( a1_minus_a0 & -a1_minus_a0 ) - 1 );
    unsigned denominator = __builtin_popcount( ( p & -p ) - 1 );
    unsigned m = numerator / denominator + ( numerator % denominator == 0 ? 1 : 2 );
    return std::min( m, n );
}

unsigned solve_p_odd( unsigned n, unsigned s, unsigned p, unsigned q ) {

    if( p == 1 )
        return q == 0 ? 1 : std::min( n, two_to_exponent / ( q & -q ) );

    if( s == 0 && q == 0 )
        return 1;

    unsigned m = 1;
    unsigned long long p_minus_1 = p - 1;
    unsigned long long a1_minus_a0 = p_minus_1 * s + q;
    unsigned long long p_to_m = p;
    unsigned long long mask = ( two_to_exponent * ( p_minus_1 & -p_minus_1 ) /
        ( a1_minus_a0 & -a1_minus_a0 ) ) -
        1;

    while( m < n && ( p_to_m & mask ) != 1 ) {
        p_to_m = p_to_m * p_to_m;
        m = m * 2;
    }

    return std::min( m, n );
}

unsigned solve( unsigned n, unsigned s, unsigned p, unsigned q ) {
    if( p % 2 == 0 )
        return solve_p_even( n, s, p, q );
    return solve_p_odd( n, s, p, q );
}

int main() {
    unsigned n, s, p, q;
    std::cin >> n >> s >> p >> q;
    std::cout << solve( n, s, p, q );
    return 0;
}