HackerRank Bit Array solution in c++ programming

In this HackerRank Bit Array problem solution in the c++ programming language, You are given four integers: N, S, P, Q. You will use them in order to create the sequence with the following pseudo-code. Your task is to calculate the number of distinct integers in sequence a.

HackerRank Bit Array problem solution in c++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;



int main() {
    unsigned long long n,s,p,q,r=0,ans=0,returned,v;
    n=100000000; s=1232077670; p=126810854; q=1536183938; //26
    // n=100000000; s=569099406; p=1607140150; q=823906344; //31
    cin>>n>>s>>p>>q;
    unsigned long long i, a0=s, a=s, ap=0, k=0, kt=0;

    v=pow(2,31);
    // v-=1;
    // cout<<bitset<64>(v)<<endl;
    // v=~v;
    // cout<<bitset<64>(v)<<endl;
    for(i=0; i<n; i++){
        // a=(a*p+q)&v;
        a=(a*p+q);
        a=a%v;
        // cout<<bitset<64>(a)<<" 1 "<<endl;
        // a&=v;
        // cout<<bitset<64>(a)<<endl;
        if((a==a0 || a==ap) && i!=0){
            k=i+1;
            break;
        }
        ap=a;
    }
    if (i==n) k=i;


    cout <<k<<endl;

    return 0;
}

Second solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

unsigned long long mask[40000000];

unsigned insert(unsigned x) {
    unsigned res = (mask[x >> 6] & (1ULL << (x & 0x3F))) == 0;
    mask[x >> 6] |= 1ULL << (x & 0x3F);
    return res;
}

int main() {
    unsigned N, S, P, Q;
    cin >> N >> S >> P >> Q;
    unsigned x = S;
    unsigned ans = 0;
    ans += insert(x);
    for (unsigned i = 1; i < N; i++) {
        x = (1LL * x * P + Q) % 2147483648;
        ans += insert(x);
    }
    cout << ans << endl;
    return 0;
}

Third solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <iostream>

#define pb push_back
#define all(x) (x).begin(), (x).end()

#ifdef KAZAR
  #define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

template<class T> inline void umax(T &a,T b){if(a < b) a = b;}
template<class T> inline void umin(T &a,T b){if(a > b) a = b;}
template<class T> inline T abs(T a){return a > 0 ? a : -a;}

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;

inline int read(){int x;scanf(" %d",&x);return x;}

const unsigned M = (1ll << 31) - 1;
const int MAX = 1 << 26;
const int K = 16;
const int MSK = (1 << K) - 1;

int kb[1 << K];
unsigned f[MAX];

int main(){

#ifdef KAZAR
  freopen("f.input","r",stdin);
  freopen("f.output","w",stdout);
  freopen("error","w",stderr);
#endif

  int n = read();
  unsigned s, p, q;
  cin >> s >> p >> q;

  f[s >> 5] |= 1u << (s & 31);
  for (int i = 1; i < n; i++) {
    s = (s * p + q) & M;
    f[s >> 5] |= 1u << (s & 31);
  }

  for (int i = 0; i < (1 << K); i++) {
    kb[i] = kb[i >> 1] + (i & 1);
  }

  int res = 0;
  for (int i = 0; i < MAX; i++) {
    res += kb[f[i] >> 16] + kb[f[i] & MSK];
  }
  printf("%d\n", res);

  return 0;
}