C++程式：找出給定序列中的不同元素

假設我們得到三個整數n、x、y和z。我們必須根據給定的整數建立一個序列，其中序列的第一個專案是(x模231)。除了第一個元素外，序列中的其他元素ai = (a(i-1) * y + z) 模 231，其中1 ≤ i ≤ n - 1。我們必須找出我們建立的序列中不同整數的數量。

因此，如果輸入類似於n = 5，x = 1，y = 2，z = 1，則輸出將為5。

唯一的值是{1, 3, 7, 15, 31}。所以答案是5。

為了解決這個問題，我們將遵循以下步驟：

  • MOD := 2^31
  • 定義一個數組temp
  • 將陣列temp的大小調整為MOD的值
  • p := x mod MOD
  • temp[p] := true
  • ans := 1
  • 對於初始化i := 1，當i < n時，更新（i增加1），執行：
    • p := ((p * y) + z) mod MOD
    • 如果temp[p]為true，則：
      • 退出迴圈
    • ans加1
    • temp[p] := true
  • 返回ans

示例

讓我們看看下面的實現，以便更好地理解：

#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

更新於：2021年10月20日

314 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告