题解 LuoguP3306 [SDOI2013] 随机数生成器
题目链接：【LuoguP3306】。
前置知识
OI-Wiki：快速幂，扩展欧几里得算法（exgcd），Baby Step, Giant Step 算法。
题意
很清楚，不说。
分析
当 \(t=x\) 时
答案很明显为 \(1\)，即在第一天就可以读到。
当 \(t\neq x\) 时
当 \(a=0\) 时
观察一下规律：
\[x_1\equiv x_1\pmod{p}
\]
\[x_2\equiv b\pmod{p}
\]
规律十分显著：
\[x_i\equiv\begin{cases}x_1&i=1\\b&i>1\end{cases}\pmod{p}
\]
可以直接特判。
当 \(a=1\) 时
观察一下规律：
\[x_1\equiv x_1\pmod{p}
\]
\[x_2\equiv x_1+b\pmod{p}
\]
\[x_3\equiv x_1+2b\pmod{p}
\]
规律十分显著：
\[x_i\equiv x_1+(i-1)b\pmod{p}
\]
\[(i-1)b\equiv x_i-x_1\pmod{p}
\]
然后就是用扩展欧几里得解同余方程了。
当 \(a>1\) 时
观察一下规律：
\[x_1\equiv x_1\pmod{p}
\]
\[x_2\equiv ax_1+b\pmod{p}
\]
\[x_3\equiv a^2x_1+ab+b\pmod{p}
\]
规律十分显著：
\[x_i\equiv a^{i-1}x_1+\sum\limits_{j=0}^{i-2}a^jb\pmod{p}
\]
很明显是一个等比数列。
等比数列如何求解？
首先设 \(S=\sum\limits_{j=0}^{i-2}a^j\)。
\[aS=\sum\limits_{j=1}^{i-1}a^j \]\[aS-S=\sum\limits_{j=1}^{i-1}a^j-\sum\limits_{j=0}^{i-2}a^j \]\[(a-1)S=a^{i-1}-1 \]\[S=\dfrac{a^{i-1}-1}{a-1} \]
\[\sum\limits_{j=0}^{i-1}a^jb = b\sum\limits_{j=0}^{i-1}a^j= b\dfrac{a^{i-1}-1}{a-1}=\dfrac{b}{1-a}-\dfrac{b}{1-a}a^{i-1}
\]
\[a^{i-1}\equiv\dfrac{x_i-\frac{b}{1-a}}{x_1-\frac{b}{1-a}}\pmod{p}
\]
\[a^{i-1}\equiv\dfrac{(a-1)x_i+b}{(a-1)x_1+b}\pmod{p}
\]
然后求逆元之后利用 BSGS 算法求解同余高次方程。
最后可以发现其实推完公式之后就是 「SDOI2011」计算器。
代码
//the code is from chenjh
#include<cstdio>
#include<cmath>
#include<unordered_map>
typedef long long LL;
LL qpow(LL a,int b,const int p){//快速幂。
int ret=1;
for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;
return ret%p;
}
int exgcd(const int a,const int b,int&x,int&y){//扩展欧几里得。
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y);
int z=x;x=y,y=z-y*(a/b);
return d;
}
LL BSGS(int a,LL b,int p){//大步小步算法。
std::unordered_map<LL,LL> h;h.clear();//std::unordered_map 基于哈希，理论上更快，实际上也比红黑树实现的 std::map 快。
b%=p;
int t=(LL)sqrt(p)+1;
for(int j=0;j<t;j++) h[b*qpow(a,j,p)%p]=j;
a=qpow(a,t,p);
if(!a) return b?-1:1;
for(int i=0;i<=t;i++){
int v=qpow(a,i,p);
LL j=h.find(v)==h.end()?-1:h[v];
if(j>=0 && (LL)i*t-j>=0) return (LL)i*t-j;
}
return -1;
}
int main(){
int T;scanf("%d",&T);
for(int p,a,b,x,t;T--;){
scanf("%d%d%d%d%d",&p,&a,&b,&x,&t);
if(x==t) puts("1");
else if(!a) puts(t==b?"2":"-1");
else if(a==1){
int X,Y;
int g=exgcd(b,p,X,Y);
int B=((LL)t-x+p)%p;
printf("%d\n",B%g?-1:int(((LL)B/g*X%(p/g)+p/g)%(p/g)+1));//求解线性同余方程。
}
else{
LL B=((LL)(a-1)*t+b)%p*qpow(((LL)(a-1)*x+b)%p,p-2,p)%p;
int ans=BSGS(a,B,p);
printf("%d\n",ans<0?-1:ans+1);
}
}
return 0;
}