주어진 시퀀스에서 고유한 요소를 찾는 C++ 프로그램

세 개의 정수 n, x, y, z가 주어졌다고 가정합니다. 시퀀스의 첫 번째 항목이 (x modulo 2 ³¹ 인 경우) 주어진 정수에서 시퀀스를 만들어야 합니다. ). 첫 번째 요소 이외의 시퀀스 a_i의 다른 요소 =(a_(i-1) * y + z) 모듈로 2 ³¹ , 여기서 1 ≤ i ≤ n - 1. 우리는 우리가 만든 시퀀스에서 고유한 정수의 수를 찾아야 합니다.

따라서 입력이 n =5, x =1, y =2, z =1과 같으면 출력은 5가 됩니다.

고유한 값은 {1, 3, 7, 15, 31}입니다. 따라서 답은 5입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 모드 :=2^31
• 배열 온도 정의
• 배열 온도를 MOD 값으로 조정
• p :=x 모드 MOD
• temp[p] :=사실
• ans :=1
• 초기화 i의 경우:=1, i
• p :=((p * y) + z) 모드 MOD
• temp[p]가 참이면 -
  • 루프에서 빠져나오기
• 1만큼 증가
• temp[p] :=사실

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

const long long MOD = 2147483648;

int solve(int n, long long x, long long y, long long z) {
   vector<bool> temp;
   temp.resize(MOD);
   long long p = x % MOD;
      temp[p] = true;
      int ans = 1;
      for (int i = 1; i < n; ++i) {
         p = ((p * y) + z) % MOD;
         if (temp[p])
            break;
         ++ans;
         temp[p] = true;
   }
   return ans;
}

int main() {
cout<< solve(5, 1, 2, 1) <<endl;
return 0;
}

입력

5, 1, 2, 1

출력

5