C++ 程序用于找出给定序列中的不同元素
c++server side programmingprogramming
假设我们给出了三个整数 n、x、y 和 z。我们必须根据给定的整数创建一个序列，其中序列的第一项是 (x modulo 231)。除了第一个元素之外，序列中的其他元素 ai = (a(i-1) * y + z) modulo 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] 为真，则 −
- 退出循环
- 将 ans 增加 1
- temp[p] := true
- return 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
