fork(8) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5.  
  6.     // set up variables and constants and read input
  7.  
  8.     unsigned int N, S, P, Q, mu, nu;
  9.  
  10.     const unsigned int m = 1 << 31;
  11.  
  12.     cin >> N >> S >> P >> Q;
  13.  
  14.     // set up sequence
  15.  
  16.     unsigned int* a = new unsigned int[N];
  17.  
  18.     a[0] = S % m;
  19.  
  20.     for (int i = 1; i < N; i++) {
  21.         a[i] = (a[i-1] * P + Q) % m;
  22.     }
  23.  
  24.     // begin cycle detection (-> floyd's algorithm)
  25.  
  26.     for (int i = 0; i < N; i++) {
  27.  
  28.         if ((2*i)+1 > N-1) {
  29.  
  30.             // no cycle found -> N distinct values, output N, clean up and terminate execution
  31.  
  32.             cout << N;
  33.             delete[] a;
  34.             return 0;
  35.  
  36.         } else if(a[i] == a[(2*i)+1]) {
  37.  
  38.             // cycle detected, break loop to proceed with algorithm
  39.  
  40.             nu = i+1;
  41.             break;
  42.         }
  43.     }
  44.  
  45.     // find first element of cycle
  46.  
  47.     for (int i = 0; i < N; i++) {
  48.  
  49.         if(a[i] == a[i+nu]) {
  50.             mu = i;
  51.             break;
  52.         }
  53.     }
  54.  
  55.     // find first reoccurence of first cycle element
  56.  
  57.     for (int i = mu+1; i < N; i++) {
  58.         if(a[mu] == a[i]) {
  59.  
  60.             // number of elements up until first repeated cycle element = number of distinct values in sequence
  61.  
  62.             cout << i;
  63.             break;
  64.         }
  65.     }
  66.  
  67.     // clean up, terminate execution
  68.  
  69.     delete[] a;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.86s 3464KB
comments (?)
stdin
copy 
100000000 1 3 1
stdout
copy 
100000000
https://ideone.com/ukUMf1
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!