Problem A - De-RNG-ed

問題

線形合同法 (S_i+1 := (A * S_i + B) mod P) により生成された疑似乱数が K 項と，その上限桁数を定める D が与えられる．このとき，この乱数系列が次に生成する項を決定できるか？
ただし，P≦10^D は素数，A，B は負でない整数である．

考え方

Incorrect 貰ったのはコーディング的な問題っぽい．
とりあえず上限までの素数リストは最初に作っておく．適当に作ったところで 100ms かからないはず．
あと簡単な枝刈りとして，K＝1 だと不明が確定し，S₀＝S₁ の場合は同じ値の連続することも分かる．あとは K＝2 で 2 値が違う場合は不明が確定する．なので以下では K＞2 を仮定する．

P が決まっているとして，3 項 S₀, S₁, S₂ の関係は
S₁ ≡ a * S₀ + b
S₂ ≡ a * S₁ + b ≡ a² * S₀ + b * (1 + a)
なので
D₁ ＝ S₁ - S₀ ≡ (a-1) * S₀ + b
D₂ ＝ S₂ - S₁ ≡ a * *1＝O(10^D/D)．

*1:a-1) * S₀ + b) ＝ a * D₁ を考えると a≡D₂・D₁^-1 がわかり，そのまま b も決まるので S_K-1 から S_K が求められる． あとは許容範囲の素数 P (max(S_i)＜P≦10^D) 全てでこの結果が一致するのか，というチェックをすれば OK．↑が O(1) なので全体もせいぜい O(π(10^D