menu zcmimi's blog

arrow_back bsgs

bsgs裸题 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __in
zc
2020-03-11 13:59

K^x \equiv 1 \pmod M

求最小的非负整数x

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

exbsgs可以,但是比较麻烦

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

zc
2020-03-08 10:54

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

zc
2020-03-07 21:58
  1. 快速幂
  2. Exgcd

    xy \equiv z \pmod p

    yx+pb = z

    可以用Exgcd求解

  3. BSGS

zc
2020-02-18 17:27
1 / 1
Search
search