สมมติว่าเราได้รับเลขจำนวนเต็มสามจำนวน n, x, y และ z เราต้องสร้างลำดับจากจำนวนเต็มที่กำหนด โดยที่รายการแรกของลำดับคือ (x modulo 2 31 ). นอกเหนือจากองค์ประกอบแรก องค์ประกอบอื่นในลำดับ ai =(a(i-1) * y + z) โมดูโล 2 31 โดยที่ 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
- อุณหภูมิ[p] :=จริง
- แทน :=1
- สำหรับการเริ่มต้น i :=1 เมื่อฉัน
- p :=((p * y) + z) MOD MOD
- ถ้า temp[p] เป็นจริง ดังนั้น −
- ออกมาจากวงจร
- เพิ่ม ans ขึ้น 1
- อุณหภูมิ[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
