「BZOJ3122」[SDOI2013] 随机数生成器

2015年5月2日4,7626

Description

Input

输入含有多组数据,第一行一个正整数T,表示这个测试点内的数据组数。

接下来T行,每行有五个整数p,a,b,X1,t,表示一组数据。保证X1和t都是合法的页码。

注意:P一定为质数

Output

共T行,每行一个整数表示他最早读到第t页是哪一天。如果他永远不会读到第t页,输出-1。

Sample Input

3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1

Sample Output

1
3
-1

HINT

0<=a<=P-1,0<=b<=P-1,2<=P<=10^9

题解

对于我这种数学渣真是太难了

给定a,b,x1,素数p

\[x_{i+1}=(ax_i+b) (mod~p)\]

求最小的n使得\(x_n=t\)

若x1=t则n=1

若a=0则判断b=t?

若a=1

\[x_n=x_1+(n-1)b\]

这个显然用exgcd可以求解

若a>=2

\[x_n=a^{n-1}x_1+b \frac {a^{n-1}-1}{a-1}(mod~p)=t\]

\[设c为a-1的逆元\]

\[(x_1+bc)a^{n-1}=bc+t(mod~p)\]

exgcd解出\(a^{n-1}\)

最后用bsgs算一下n即可

 

说点什么

提醒
avatar
小李飞刀
小李飞刀

640 1 192 6 454

小李飞刀
小李飞刀

黄学长,似乎a=1的时候解出来的x不能保证是最小的吧?
是不是应该需要取膜?
如果是下面这组数据您的程序似乎出来的不是最小解:

trackback

[…] 题解戳这里:http://hzwer.com/6963.html […]

233
233

printf(“HAHAHA”)

De℃,.: )
De℃,.: )

BZOJ!