K - 乱数調整
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
問題
背景
ゲーム研究者のビッグブリッジ伯爵は、SOUND VERTEX III - GRAPH WARS というゲームの乱数生成にLFSR (日本語版 Wikipedia) という乱数生成方式が使われていることを発見した。
合法的にチートをする最高のパフォーマンスを発揮するために、乱数生成器の内部状態が特定の値となるタイミングを知りたい。
課題
三つの非負整数A, B, Xが与えられる。 0 以上の任意の整数 t に対して、乱数生成器の時刻 t での内部状態 a_t は次の式で与えられる。
- a_0\ =\ A
- a_{t+1}\ =\ (a_t\ /\ 2)\ \^\ (a_t\ %\ 2\ \times\ B)
ただし、" \times ", "/", "%"はそれぞれ整数での乗算, 除算, 剰余算、"^"は二進数表現でのビットごとのxor演算を表す。
a_t = X となる最小の t を出力せよ。 そのような t が存在しない場合は -1 を出力すること。
配点
300
入力
入力は以下の形式で与えられる。
A B X
制約
- 0 ≤ A, B, X < 2^{36}
部分点
この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。
- 0 ≤ A, B, X < 2^{10}
出力
a_t = X となるような最小の t を一行で出力せよ。
入力例1
7 6 5
出力例1
1
a_0 = 7, a_1 = (7 / 2) \^ 6 = 5 なので t = 1 となる。
入力例2
9 6 1
出力例2
2
a_0 = 9, a_1 = 2, a_2 = 1 である。
入力例3
3 4 6
出力例3
2
入力例4
8 7 6
出力例4
-1