2013年3月百度之星A題

偽隨機數生成器

題目描述

?baidu熊最近在學習隨機算法，于是他決定自己做一個隨機數生成器。

這個隨機數生成器通過三個參數c, q, n作為種子, 然后它就可以通過以下方式生成偽隨機數序列：

m₀=?c,

m_i+1= (q²m_i?+ 1) mod 2ⁿ, ? ?for all?i?>= 0.

?

因為一些奇怪的原因，q 一定是奇數。現在du熊想知道對于一個給定的數 x ，是不是會出現在這個偽隨機數序列里面，如果存在的話，他還想知道最早是在哪里出現，即給定一個整數 x ，要求找出一個最小的整數 k 滿足?m_k=?x.

輸入格式

輸入包含多組數據。

每個測試數據包含一行三個整數: c, q, n, x.

數據滿足0 <=?c?< 2ⁿ, 0 <=?q²?< 2⁶³, 0 < n <= 63, 0 <= x < 2⁶³.

輸入以文件結束符結尾。

輸出格式

對應每個測試數據輸出滿足條件的k，如果x不會出現在序列里面的話，就輸出-1。

樣例輸入

1 3 3 5

1 3 2 5

樣例輸出

4

-1

這道題第一感覺覺得應該是用費馬小定理或者歐拉定理之類的東西，再分析遞推，后來才發現想錯了，浪費了很多時間，暫時也不知道代碼寫的對不對，測試了幾組都是對的，到時候確認了再發代碼吧。

很容易知道循環節是2^n，白曄說當n充分小的時候，Mi=i+c(mod2^n).........如果n過大，就得加上一個2^m。。那是不是不會通過所有的數據。。。

?