zcmimi's blog

arrow_backbsgs共7篇文章

avatar
zc
2020-03-11 13:59:00
查看原题

点击跳转

bsgs裸题

avatar
zc
2020-03-08 10:54:00
查看原题

点击跳转

K^x \equiv 1 \pmod M

求最小的非负整数x

最近刚学了bsgs,一眼看成exbsgs

exbsgs可以,但是比较麻烦

看到最后是1,我们可以想到欧拉定理:

K^{\varphi(M)} \equiv 1 \pmod M(\gcd(K,M)=1)

可以发现,答案是\varphi(M)的约数,那么枚举\varphi(M)的约数即可(可以一直尝试枚举删掉约数)

\gcd(K,M)!=1时无解

avatar
zc
2020-03-07 21:58:00
查看原题

点击跳转

\overbrace{111\dots111}^{\text{N个1}} \equiv k \pmod m \\ \frac{10^N-1}9\equiv k \pmod m \\ 10^N\equiv 9k+1 \pmod m

顺利地推出是bsgs,(m是质数,也就不用exbsgs了)

avatar
zc
2020-02-25 17:16:00
查看原题

点击跳转

bsgs模板题

avatar
zc
2020-02-24 13:59:00
查看原题

点击跳转

我们要做的是强行将式子转换为bsgs能求解的形式(求y^x\equiv z \pmod p)

X_{i+1} \equiv aX_i+b \pmod p \\ X_{i+1} + \frac ba \equiv aX_i+b+\frac ba \pmod p \\ aX_{i+1} + b \equiv a^2X_i+ab+b \pmod p \\ X_{i+2} \equiv a^2X_i+ab + b \pmod p

继续往下推,并根据等比数列的公式可以得到:

X_i \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p

带入t\equiv X_i \pmod p,得

t \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p \\ (1-a)t \equiv (1-a)a^{i-1}X_1+b(1-a^{i-1}) \pmod p \\ t-at \equiv a^{i-1}(X_1-aX_1)+b-b\cdot a^{i-1} \pmod p \\ a^{i-1}(X_1-aX_1-b)\equiv t-at-b \pmod p \\ a^{i-1}\equiv \frac{t-at-b}{X_1-aX_1-b} \pmod p

成功强行转换

可以用bsgs求解了!

还没完,要考虑一下几种特殊情况:

  1. X_1=t

    第一天就可以读到

  2. a=1

    题目变为X_1+kb \equiv t \pmod p

    因为p是质数,所以可以直接用费马小定理求逆元

    b=0时无解

  3. a=0

    判断b=t

avatar
zc
2020-02-18 21:05:00
查看原题

点击跳转

avatar
zc
2020-02-18 17:27:00
查看原题

点击跳转

  1. 快速幂
  2. Exgcd

    xy \equiv z \pmod p

    yx+pb = z

    可以用Exgcd求解

  3. 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的时候复杂度最优,\Theta(\sqrt p)

1/1
Search
search