BSGS代码

在OI数学笔记三中，我写过BSGS算法，这里是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int z[1005];
void bsgs(int a, int b, int p) {
    int sp = int(sqrt(p));
    z[0] = 1;
    for(int i = 1; i < sp; i++)
        z[i] = 1ll * z[i - 1] * a % p;
    for(int i = 0; i < sp; i++)
        if(z[i] % p == b) return i;
    sort(z, z + sp);
    int asp = fastPower(a, sp, p);
    for(int i = 2, l = sp, r = sp + sp - 1; l <= n; l += sp, r += sp, i++) {
        int div = fastPower(asp, i - 1, p);
        div = fastPower(div, p - 2, p);
        int v = 1ll * b * div % p;
        binary(); //二分查找v在第一组是否出现
    }
    return -1;
}