BZOJ 3122 SDOI2013 随机数生成器 数论 EXBSGS
首先讨论特殊情况
若X1=t ans=1
若a=0 ans=b==t?2:-1
若a=1 X1+b*(ans-1)==t (%p) 扩展欧几里得
令
temp=b/(a-1)
则有
(X(i+1)+temp)=a*(Xi+temp)
Xans=(X1+temp)*a^(ans-1)-temp
其中Xans%p=t
则有
(X1+temp)*a^(ans-1)-temp == t (%p)
两侧同乘a-1得
(a*X1-X1+b)*a^(ans-1) == (a-1)*t+b (%p)
令
Y=a*X1-X1+b
Z=a*t-t+b
Y*a^(ans-1) == Z(%p)
将Y和p约分
若Z%gcd(Y,p)!=0 return -1
令
A=a
B=Z*Y^-1
C=p
x=ans-1
A^x==B(%C)
//就是先搞个等比数列，再求个逆元，再BGSG
评论