bzoj 3122 [Sdoi2013]随机数生成器（逆元，BSGS）

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

【思路】

逆元，BSGS算法

首先特判：a=0，a=1，当a=1时，序列为:

x1,x1+b,x1+2*b …

即(x1+(n-1)*b) mod p=t，用个乘法逆元可以求出，当逆元为0的时候无解输出-1。

当a>=2时

可以得到通项公式：

xn=[ a^n-1 *(x1+b/(a-1))-b/(a-1) ] mod p

若满足xn=t，则有

a^n-1 = (b* (a-1)^-1 +t) * (b*(a-1)^-1+x1)^-1 mod p

于是可以用BSGS算法求n-1。

需要注意的是各种取模p一定要有。

【代码】

 1 #include<map>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int N = 1e4+5;
 9 
10 LL pow(LL x,LL p,LL MOD) {
11     LL ans=1;
12     while(p) {
13         if(p&1) ans=(ans*x)%MOD;
14         x=(x*x)%MOD;
15         p>>=1;
16     }
17     return ans;
18 }
19 map<LL,int> mp;
20 LL BSGS(LL a,LL b,LL MOD) {
21     a%=MOD;
22     int m=sqrt(MOD)+1; mp.clear();
23     LL am=pow(pow(a,m,MOD),MOD-2,MOD);
24     LL x=1; mp[1]=0;
25     for(int i=1;i<m;i++) {
26         x=(x*a)%MOD;
27         if(!mp.count(x)) mp[x]=i;
28     }
29     for(int i=0;i<m;i++) {
30         if(mp.count(b)) return i*m+mp[b];
31         b=(b*am)%MOD;
32     }
33     return -2;
34 }
35 
36 LL p,a,b,x1,t;
37 
38 int main() {
39     //freopen("in.in","r",stdin);
40     //freopen("out.out","w",stdout);
41     int T;
42     scanf("%d",&T);
43     while(T--) {
44         cin>>p>>a>>b>>x1>>t;
45         LL c=pow(a-1,p-2,p),d,x,y,con,inv;
46         if(x1==t) puts("1"); else
47         if(!a) {
48             if(t==b) puts("2");
49             else puts("-1");
50         } else
51         if(a==1) {
52             inv=pow(b,p-2,p);
53             if(!inv) puts("-1");
54             else printf("%lld
",((inv*(t-x1+p)%p)+p)%p+1);
55         } else {
56             con=((((b*c+t)%p)*(pow((x1+b*c)%p,p-2,p)))%p+p)%p;
57             printf("%lld
",BSGS(a,con,p)+1);
58         }
59     }
60     return 0;
61 }