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

 

 

 


 

 

 

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

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

第 \(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\) 的点,特判不清楚的话就。。。。。

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注