特定のシーケンスで個別の要素を見つけるためのC++プログラム

3つの整数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です。

これを解決するには、次の手順に従います-

• MOD：=2 ^ 31
• アレイの温度を定義する
• 配列の温度をMODの値に変更します
• p：=x mod MOD
• temp [p]：=true
• ans：=1
• iを初期化する場合：=1、i
• p：=（（p * y）+ z）mod MOD
• temp [p]がtrueの場合、-
  • ループから抜け出す
• ansを1増やします
• temp [p]：=true

例

理解を深めるために、次の実装を見てみましょう-

#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