【bzoj3122】[Sdoi2013]随机数生成器

2015年5月2日3,4216

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即可

 

  • De℃,.: )2015年5月3日 下午1:50 回复

    BZOJ!

    #1  
  • 2332016年1月9日 下午10:05 回复

    printf(“HAHAHA”)

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

    #3  
  • 小李飞刀2017年2月16日 上午8:51 回复

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

    #4  
  • 小李飞刀2017年2月16日 上午8:51 回复

    640 1 192 6 454

    #5  
  • […] 黄学长博客 以后还是不可以偷懒将变量名取作 xx, xxx, yy 了,因为把 xx 写成了 x, debug […]

    #6