BSGS代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}