<a href="http://en.wikipedia.org/wiki/Linear_congruential_generator" rel="nofollow">Wikipedia</a>によれば、線形合同法

Question

のk番目の最小数を計算する方法、線形合同法は、以下の漸化式で定義される。

0 < m、 0 <= a < m、 0 <= c < m、 0 <= X(0) < mは整数で

X(n) = {a.X(n-1) + c} mod m 

ジェネレータを指定する定数。

a、c、m、X(0)、及びnが与えられ、iの値がセット{X(0), X(1), ..., X(n)}非常に高速のk番目の最小値（1 <= k <= n）を決定することができますか？その後、

(n >= m)なら...あなたが生成中にk最低のアイテムを格納していないと仮定すると、

Answer 1

- （O(n)よりも高速なアルゴリズムをソートすることにより、ベース）と定数は、全期間（ref here）の基準を満たしますk番目の最小アイテムはk-1になります。

(n >= m)と定数が基準を満たしていないか、(n < m)は、あなたが終了することができ、線形探索を行う必要がある場合k-1ある日に最低番目k場合。