首页 / 更多教程 / BZOJ 3122 随机数生成器
BZOJ 3122 随机数生成器
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了BZOJ 3122 随机数生成器，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2498字，纯文字阅读大概需要4分钟。
内容图文
http://www.lydsy.com/JudgeOnline/problem.php?id=3122
题意:给出p,a,b,x1,t
已知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求就可以了
1 #include<algorithm>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 #include<iostream>
6 #include<map>
7#define ll long long
8ll p;
9ll read(){
10char ch=getchar();ll t=0,f=1;
11while (ch<‘0‘||ch>‘9‘){if (ch==‘-‘) f=-1;ch=getchar();}
12while (‘0‘<=ch&&ch<=‘9‘){t=t*10+ch-‘0‘;ch=getchar();}
13return t*f;
14}
15ll Pow(ll x,ll y){
16 ll res=1;
17if (x<0) x=(x+p)%p;
18while (y){
19if (y%2) res=(res*x)%p;
20 x=(x*x)%p;
21 y/=2;
22 }
23return res;
24}
25ll gcd(ll a,ll b){
26if (b==0) return a;
27elsereturn gcd(b,a%b);
28}
29void exgcd(ll a,ll b,ll &x,ll &y){
30if (b==0){
31 x=1;
32 y=0;
33return;
34 }
35 exgcd(b,a%b,x,y);
36 ll T=x;
37 x=y;
38 y=T-(a/b)*y;
39}
40ll reverse(ll X){
41 ll A=X,B=p;
42 ll x,y;
43 exgcd(A,B,x,y);
44return (x%p+p)%p;
45}
46ll work(ll a,ll b){
47 a%=p;
48if (a==0){
49if (b==0) return1;
50elsereturn -1;
51 }
52 std::map<ll,int> mp;
53 ll m=sqrt(p)+1,I=1,Im=Pow(a,p-1-m),t=1;
54 mp.clear();mp[1]=m+1;
55for (int i=1;i<m;i++){
56 t=t*a%p;
57if (!mp[t]) mp[t]=i;
58 }
59for (int k=0;k<m;k++){
60int i=mp[I*b%p];
61if (i){
62if (i==m+1) i=0;
63return i+k*m;
64 }
65 I=I*Im%p;
66 }
67return -1;
68}
69ll solve(ll a,ll b,ll x1,ll t){
70if (t==x1) {
71return1;
72 }
73if (a==0){
74if (b==t){
75return2;
76 }
77return -1;
78 }
79if (a==1){
80 ll A=b,B=p,T=(t-x1+p)%p;
81 ll D=gcd(A,B);
82if (T%D) {
83return -1;
84 }
85 T/=D;
86 ll x,y;
87 exgcd(A,B,x,y);
88 x=(x*T)%p;
89while (x<0) x+=p;
90return x+1;
91 }
92 ll c=Pow(a-1,p-2);
93 ll A=(b*c+x1)%p,B=p,T=(b*c+t)%p;
94if (A<0) A=(A+p)%p;
95if (B<0) B=(B+p)%p;
96 ll D=gcd(A,B);
97if (T%D){
98return -1;
99 }
100 T/=D;
101 ll x,y;
102 exgcd(A,B,x,y);
103while (x<0) x=(x+p)%p;
104 x=(x*T)%p;
105 ll ans=work(a,x);
106if (ans!=-1) return ans+1;
107elsereturn ans;
108}
109int main(){
110int Tcase;
111 scanf("%d",&Tcase);
112while (Tcase--){
113 ll a,b,x1,t;
114 p=read();a=read();b=read();x1=read();t=read();
115 printf("%lld\n",solve(a,b,x1,t));
116 }
117 }
原文：http://www.cnblogs.com/qzqzgfy/p/5581955.html
内容总结
以上是互联网集市为您收集整理的BZOJ 3122 随机数生成器全部内容，希望文章能够帮你解决BZOJ 3122 随机数生成器所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。