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$ 是质数。

 

 

 

---

 

 

 

稍微推一下式子就会发现这是模板题

可以把每一项都展开，找找规律，或者直接等比数列求和：

第 $n$ 项为：$a^{n-1}k-(a^{n-2}+a^{n-3}+…+a+1)b \bmod p$

即：$a^{n-1}k-\frac{a^{n-1}-1}{a-1} b \bmod p$

令其同余于 $t$ ，则有：

$a^{n-1}k-\frac{a^{n-1}-1}{a-1} b\equiv t\pmod p$

即：$a^{n-1}\equiv \frac{t-\frac{b}{a-1}}{k-\frac{b}{a-1}}\pmod p$

发现右边是常数，那就是一个 BSGS 了。

BSGS 一种比较好的写法：

有 $a^n \equiv t (\bmod p)$ ，求 $n$ 最小正整数解。

可以发现 $n < p$ ，所以可以设 $n=Ax-B$，其中 $x=\lfloor \sqrt p \rfloor, 1 \leq A \leq x, 0 \leq B<x$ 。

所以 $a^{Ax} \equiv t+a^B (\bmod p)$ ，用一个 hash_table 存值即可。

还有本题要特别注意 $a=0$，$a=1$ 的点，特判不清楚的话就。。。。。