时间限制：1234MS 内存限制：43210KB
难度：6.5 （既然是自己搬的题还是正常一点吧w）
定义模意义下的递推数列 \displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.，其中模数为 1000000009 。
给定整数 c（0 \leq c < 1000000009），求出它最早出现在数列的哪个位置，并输出下标。
若 c 永远不会出现在此数列的任一位置，则输出 -1 。
多组数据。
第一行一个正整数 T （0 < T \leq 100） 表示 T 组数据。
接下来 T 行每行一个数表示每组数据的 c 。
对于每组数据，输出一行一个数表示答案。
时间限制：1000MS 内存限制：262144KB
难度：6.0
有一个随机数生成器，可以生成 0 ~ p-1 之间的伪随机整数。在生成之前，需要设定一个随机数种子 k （0 \leq k < p），则生成器第 1 次生成的整数为 k。该随机数生成器有 2 个参数 a, b，如果第 i 次生成的整数为 x，则第 i+1 次生成的整数为 (ax+b) \bmod p 。
现给定整数 t ，我们的问题是，该随机数生成器至少需要生成多少个数，才能生成得到 t？
对于给定的 p,a,b,k,t ，请计算要使随机数生成器生成整数 t，所需生成数的次数的最小值。
多组数据。第一行一个整数 T 表示数据组数，T \leq 50 。
接下来 T 行，每行五个整数 p,a,b,k,t 表示一组数据，其中 0 \leq a,b,k,t < p 。
对于每组数据，将随机数生成器的最小生成次数输出到文件中。
如果该随机数生成器无法生成整数 t，输出 -1 。
对于 20\% 的数据，p \leq 100 。
对于另外 30\% 的数据，a=1 。
对于另外 30\% 的数据，b=0 。
对于 100\% 的数据，p \leq 10^9 且 p 是质数。