用于解决$y^x \equiv z\ (mod\ p)$，给定$y,z,p \geq 1$，求解$x$。
当$gcd(y,p)=1$，在这种情况下，有可能给定$p$为质数。设$x=a * m - b$ ，$m= \lceil \sqrt p \rceil$，$ a \in [0,m+1)$，$b \in [0,m)$，那么原式变成$y^{a * m}=z * y^{b}$，先枚举$b$，计算$z * y^{b}(mod\ p)$，存到$map$中，再枚举$a$就好了。
SDOI2011
题意：给定$y,z,p$，计算1. $y^z (mod \ p)$；2. 满足$x * y \equiv z(mod \ p)$的最小非负整数的$x$；3.满足$y^x \equiv z\ (mod\ p)$的最小非负整数的$x$。
1 |
|
当$gcd(y,p) \neq 1$时，就要用到$exgcd$理论。
将原式写成$y * y^{x-1}+k * p=z,k \in Z$，根据$exgcd$，当$d=gcd(y,p)$不是$z$的约数就不会有解，有：$$\frac{y}{d} * y^{x-1}+k * \frac{p}{d}=\frac{z}{d}$$
一直递归直到$d=1$，设之间的所有的$d$的乘积为$g$，递归$c$次，令$x’=x-c\ ,\ p’=\frac{p}{g}\ ,\ z=\frac{z}{g}$，$y^{x’} * \frac{y^c}{g} \equiv z’(mod \ p’)$
然后再用BSGS求解。
SPOJMOD Power Modulo Inverted
1 |
|
generator 2
2019年牛客多校第五场。
题意：你有一个$n$个数字的递推式：$x_{i} \equiv (a * x_{i-1} + b)mod \ p$ ，给定$n$，$x_0$，$a$，$b$，$p$，其中$p$是素数，询问$Q$次，求一个最小的下标$i$，使得$x_i \equiv v (mod \ p)$。
题解：很容易得到关于$x_i$的通项公式：$$x_i = a^i * x_0 + b * \sum_{j=0}^{i-1} a^j = a^i * x_0 + b * (\frac{a^i - 1}{a - 1}) = a ^ i * (\frac{b}{a-1}+x_0) - \frac{b}{a-1}$$
那么，可以化成$$a^i \equiv \frac{(a-1) * v+b}{(a-1) * x_0+b} (mod \ p)$$
由于题目需要查询的次数有$1000$次，直接套上面的$BSGS$复杂度太大，所以就需要预处理，我们看上面的代码，每次进行算法时其实都有一次for循环是预处理，我们把这一步放在查询前，改用unorder_map或者手写hash存值。
进一步优化，我们把预处理的时间增加，而减少查询时间，将预处理改成$\left \lceil p^{\frac{2}{3}} \right \rceil$，然后将查询的时间改成$\left \lceil p^{\frac{1}{3}} \right \rceil$。
注意这题$a$等于1或者0需要特判。
1 |
|
