首页 > 代码库 > 【BZOJ 3122】 [Sdoi2013]随机数生成器 (BSGS)
【BZOJ 3122】 [Sdoi2013]随机数生成器 (BSGS)
3122: [Sdoi2013]随机数生成器
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1442 Solved: 552Description
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
-1HINT
0<=a<=P-1,0<=b<=P-1,2<=P<=10^9
.jpg)
【分析】
这题简直坑爹到家了！！p是质数不说，还有各种恶心特判！！！！
a=0，a=1，b=0都要特判。
虽说自己推出了通项公式，但是哪里的除法可以逆元哪里不可以都不知道，一开始通分各种wa！！
看别人的题解吧：
已知xn=a*xn-1+b%p，求最小的n令xn=t
首先，若x1=t，则返回1
若a=0，则若b=t 返回2，否则无解
若a=1，则T=t-x1+p%p，可以列出方程
b*x+p*y==T % p
若a>=2，则根据等比数列和可得
xn=t=x1*a^(n-1)+b*(a^(n-1)-1)/(a-1) %p
由于p为质数，所以令c=inv[a-1]=(a-1)^(p-2)
x1*a^(n-1)+b*c*(a^(n-1))==b*c+t %p
(x1+b*c)*(a^(n-1))==b*c+t % p
令A=x1+b*c,B=p,C=b*c+t
则就是解A*X+B*Y==C %p
解出来X=a^(n-1),然后这个用BSGS求就可以了
http://www.cnblogs.com/qzqzgfy/p/5581955.html
我的代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define LL long long 10 #define Maxn 35000 11 12 struct node 13 { 14 LL id,val; 15 }t[Maxn]; 16 17 LL ax,ay; 18 LL exgcd(LL a,LL b) 19 { 20 if(b==0) {ax=1;ay=0;return a;} 21 LL g=exgcd(b,a%b); 22 LL xx=ax; 23 ax=ay;ay=xx-(a/b)*ay; 24 return g; 25 } 26 27 bool cmp(node x,node y) {return (x.val==y.val)?(x.id<y.id):(x.val<y.val);} 28 29 LL cnt; 30 31 LL t_div(LL x) 32 { 33 LL l=0,r=cnt; 34 while(l<r) 35 { 36 LL mid=(l+r)>>1; 37 if(t[mid].val==x) return t[mid].id; 38 if(t[mid].val>x) r=mid-1; 39 else l=mid+1; 40 } 41 if(t[l].val==x) return t[l].id; 42 return -1; 43 } 44 45 LL get_ans(LL k,LL a,LL c,LL p) 46 { 47 LL sq=(LL)ceil(sqrt((double)p)); 48 t[0].id=0;t[0].val=k%p; 49 for(LL i=1;i<=sq;i++) t[i].val=(t[i-1].val*a)%p,t[i].id=i; 50 51 sort(t+1,t+1+sq,cmp); 52 cnt=0; 53 for(LL i=1;i<=sq;i++) if(t[i].val!=t[i-1].val) t[++cnt]=t[i]; 54 55 LL bm=1; 56 for(LL i=1;i<=sq;i++) bm=(bm*a)%p; 57 LL g=exgcd(bm,p); 58 ax=(ax%(p/g)+(p/g))%(p/g); 59 bm=ax; 60 61 LL tmp=c%p; 62 for(LL i=0;i<=sq;i++) 63 { 64 LL now=t_div(tmp); 65 if(now!=-1) return now+i*sq; 66 tmp=(tmp*bm)%p; 67 } 68 return -1; 69 } 70 71 LL ffind(LL k,LL a,LL c,LL p) 72 { 73 LL x=k; 74 for(LL i=0;i<=100;i++) 75 { 76 if(x==c) return i; 77 x=(x*a)%p; 78 } 79 LL g; 80 x=0; 81 while((g=exgcd(a,p))!=1) 82 { 83 p/=g; 84 k=(k*(a/g))%p; 85 if(c%g!=0) return -1; 86 c/=g; 87 x++; 88 } 89 LL ans=get_ans(k,a,c,p); 90 if(ans==-1) return -1; 91 return ans+x; 92 } 93 94 int main() 95 { 96 int T,kase=0; 97 scanf("%d",&T); 98 while(T--) 99 {100 // printf("%d: ",++kase);101 LL p,a,b,x,t,c;102 scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x,&t);103 // if(b==0) {printf("1\n");continue;}104 if(t==x) {printf("1\n");continue;}105 if(a==0&&b==t) {printf("2\n");continue;}106 else if(a==0) {printf("-1\n");continue;}107 if(a==1)108 {109 LL g=exgcd(b,p);110 c=t-x;c=(c%p+p)%p;111 if(c%g!=0) {printf("-1\n");continue;}112 ax*=c/g;113 ax=(ax%(p/g)+(p/g))%(p/g);114 printf("%d\n",ax+1);115 continue;116 }117 118 LL phi;119 if(b%(a-1)==0) phi=b/(a-1);120 else121 {122 if(exgcd(a-1,p)!=1) {printf("-1\n");continue;}123 ax=(ax%p+p)%p;124 phi=(b*ax)%p;125 }126 LL A=x+phi,B=phi+t;127 128 if(b==0) A=x,B=t;129 130 A=(A%p+p)%p; B=(B%p+p)%p;131 // if(A==0) {printf("-1\n");continue;}132 133 LL ans=ffind(A,a,B,p);134 135 if(ans==-1) printf("-1\n");136 else printf("%lld\n",ans+1);137 }138 return 0;139 }
2016-09-05 18:24:44
【BZOJ 3122】 [Sdoi2013]随机数生成器 (BSGS)