← 返回题目列表

AtCoder · utpc2014_k

K. 随机数调整

中文机器翻译题面 查看原题

問題

背景

游戏研究员 Earl Bigbridge 使用 LFSR (日文版维基百科 我发现使用了一种名为的随机数生成方法。 合法作弊我想知道随机数生成器的内部状态何时达到特定值才能达到最佳性能。

課題

三个非负整数 任何大于或等于A, B, X。 表示 0 的整数 对于 t ,随机数生成器时间 t 处的内部状态 a_t 由下式给出。

  • a_0\ =\ A
  • a_{t+1}\ =\ (a_t\ /\ 2)\ \^\ (a_t\ %\ 2\ \times\ B)

但是,“ \times "、"/" 和"%" 分别表示整数乘法、除法和求余运算,"^" 表示二进制表示中的按位异或运算。

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