分类： BSGS

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制：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\) 。

  • 输出格式

对于每组数据，输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source： BZOJ 5104…

YZOJ P3451 [SDOI2013]随机数生成器问题

YZOJ P3451 [SDOI2013]随机数生成器问题

时间限制：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\) 是质数。

 

 …