「BZOJ3122」[SDOI2013] 随机数生成器
Description
.jpg)
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
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1
Sample Output
1
3
-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即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<map> #include<cmath> #include<cstdio> #include<iostream> #include<algorithm> #define ll long long using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int T; ll p,a,b,x1,t; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){x=1;y=0;return a;} ll tmp=exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; return tmp; } ll kpow(ll a,ll b,ll p) { a%=p;ll ans=1; for(ll i=b;i;i>>=1,a=a*a%p) if(i&1)ans=ans*a%p; return ans; } map<ll,int> mp; ll bsgs(ll A,ll B,ll C) { A%=C; if(!A) { if(!B)return 1; return -1; } ll m=sqrt(C)+1,t=1,I=1,Im=kpow(A,C-1-m,C); mp.clear();mp[1]=m+1; for(int i=1;i<m;i++) { t=t*A%C; if(!mp[t])mp[t]=i; } for(int k=0;k<m;k++) { int i=mp[B*I%C]; if(i) { if(i==m+1)i=0; return k*m+i; } I=I*Im%C; } return -1; } ll cal1() { ll C=(t-x1+p)%p,x,y; ll t=exgcd(b,p,x,y); if(C%t)return -1;C/=t; x=x*C%p; if(x<0)x+=p; return x+1; } ll cal2() { ll c=kpow(a-1,p-2,p),A=(x1+b*c)%p,C=(t+b*c)%p,x,y; ll t=exgcd(A,p,x,y); if(C%t)return -1;C/=t; if(x<p)x=x%p+p; t=bsgs(a,x*C%p,p); if(t!=-1)return t+1; return -1; } ll solve() { if(x1==t)return 1; if(a==0) { if(b==t)return 2; return -1; } if(a==1)return cal1(); else return cal2(); } int main() { T=read(); while(T--) { p=read();a=read();b=read();x1=read();t=read(); printf("%lld\n",solve()); } return 0; } |
计数器 9756404
OI 课件=>
OI 课件=>
640 1 192 6 454
黄学长，似乎a=1的时候解出来的x不能保证是最小的吧？
是不是应该需要取膜？
如果是下面这组数据您的程序似乎出来的不是最小解：
[…] 题解戳这里：http://hzwer.com/6963.html […]
printf(“HAHAHA”)
BZOJ!