B. Санамсаргүй дарааллын үе

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарп саяхнаас санамсаргүй дарааллын тоонуудыг сонирхдог болов. Тэрээр олон програмчлалын хэл дараах байдлаар тоо үүсгэдгийг сурлаа: ($i ≥ 1$). Энд $a$, $b$, $m$ нь тогтмол санамсаргүй тоонуудыг үүсгэгч бөгөөд, $r_{0}$ нь $randseed$ гэж нэрлэгддэг санамсаргүйн эхний тоо юм (энэ утгыг $RandSeed(r)$ юмуу $srand(n)$ шиг гаргаж болно), нь үлдэгдэлтэй хуваах үйлдэл юм.

Жишээлбэл, хэрвээ $a = 2, b = 6, m = 12, r_{0} = 11$, бол үүссэн санамсаргүй дараалал нь: $4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ...$ байна.

Поликарп энэ дараалал эрт, орой ямар ч байсан үелдэг, энэ нь яг эхнээсээ байх албагүй гэдгийг ойлголоо. Энэ жишээнд үеийн өмнөх хэсгийн урт нь 1 ба үеийн урт нь 2 байна.

Таны даалгавар бол $a, b, m$, $r_{0}$ утгууд өгөгдсөнөөр дарааллын үеийг олох юм. Энгийнээр хэлвэл ямар нэг $k$ тооноос эхлээд $i ≥ k$ байр $i$ тоо бүрийн хувьд: $r_{i} = r_{i + t}$ байдаг хамгийн бага $t$ тоог олох юм.

Оролт

Ганц мөрөнд $a$, $b$, $m$, $r_{0}$ ($1 ≤ m ≤ 10^{5}, 0 ≤ a, b ≤ 1000, 0 ≤ r_{0} < m$) тоонууд зайгаар тусгаарлагдан өгөгднө.

Гаралт

Дарааллын үе болох ганц тоог хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
2 6 12 11
Гаралт
2
Оролт
2 3 5 1
Гаралт
4
Оролт
3 6 81 9
Гаралт
1

Тэмдэглэл

Эхний жишээний хувьд дээр үзүүлсэн.

Хоёрдугаар жишээний хувьд дараалал маань (эхний элементээсээ эхлэсэн): $0, 3, 4, 1, 0, 3, 4, 1, 0, ...$ байна.

Гуравдугаар жишээний хувьд дараалал маань (эхний элементээсээ эхлэсэн): $33, 24, 78, 78, 78, 78, ...$ байна.

Сэтгэгдлүүдийг ачааллаж байна...