LG 2485 [SDOI2011]计算器

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转快速幂 Exgcd$xy \equiv z \pmod p$$yx+pb = z$可以用 Exgcd 求解 bsgs 求解关于$x$的方程:$$y^x \equiv z \pmod p$$其中$\gcd(y,p)=1$解法:设$x=am-b$那么$y^{am} \equiv z \cdot y^b \pmod p$右边:枚举$b$的取值$[0,m-1]$,计算右边的值,存入哈希表左边:枚举可能的$a$,也就是$[1,m]$,若左边的值在哈希表中出现过,那么当前$a$合法不难证明当$m=\sqrt p……