kuangbin的BSGS：
c为素数；
#define MOD 76543
int hs[MOD],head[MOD],next[MOD],id[MOD],top;
void insert(int x,int y)
{
int k = x%MOD;
hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;
}
int find(int x)
{
int k = x%MOD;
for(int i = head[k]; i != -; i = next[i])
if(hs[i] == x)
return id[i];
return -;
}
int BSGS(int a,int b,int n)
{
memset(head,-,sizeof(head));
top = ;
if(b == )return ;
int m = sqrt(n*1.0), j;
long long x = , p = ;
for(int i = ; i < m; ++i, p = p*a%n)insert(p*b%n,i);
for(long long i = m; ;i += m)
{
if( (j = find(x = x*p%n)) != - )return i-j;
if(i > n)break;
}
return -;
}
扩展BSGS:
const int MAXN= ;
struct LINK{
ll data;
ll j;
ll next;
}HASH_LINK[];
ll ad, head[MAXN]; ll Gcd(ll a, ll b){
return b ? Gcd(b, a % b) : a;
} ll Ext_Gcd(ll a, ll b, ll &x, ll &y){
if(!b){
x = ; y = ;
return a;
}
ll r = Ext_Gcd(b, a % b, x, y);
ll t = x; x = y; y = t - a / b * y;
return r;
} ll POWER(ll a, ll b, ll c){
ll ans = ;
while(b){
if(b & ) ans = ans * a % c;
a = a * a % c;
b >>= ;
}
return ans;
} void init(){
memset(head, -, sizeof(head));
ad = ;
} ll Hash(ll a){
return a % MAXN;
} void INSERT_HASH(ll i, ll buf){
ll hs = Hash(buf), tail;
for(tail = head[hs]; ~tail; tail = HASH_LINK[tail]. next)
if(buf == HASH_LINK[tail]. data) return;
HASH_LINK[ad]. data = buf;
HASH_LINK[ad]. j = i;
HASH_LINK[ad]. next = head[hs];
head[hs] = ad ++;
} ll BSGS(ll a, ll b, ll c){
ll i, buf, m, temp, g, D, x, y, n = ;
for(i = , buf = ; i < ; i ++, buf = buf * a % c)
if(buf == b) return i;
D = ;
while((g = Gcd(a, c)) != ){
if(b % g) return -; // g | b 不满足，则说明无解
b /= g;
c /= g;
D = D * a / g % c;
++ n;
}
init();
m = ceil(sqrt((long double) c));
for(i = , buf = ; i <= m; buf = buf * a % c, i ++) INSERT_HASH(i, buf);
for(i = , temp = POWER(a, m, c), buf = D; i <= m; i ++, buf = temp * buf % c){
Ext_Gcd(buf, c, x, y);
x = ((x * b) % c + c) % c;
for(ll tail = head[Hash(x)]; ~tail; tail = HASH_LINK[tail].next)
if(HASH_LINK[tail]. data == x) return HASH_LINK[tail].j + n + i * m;
}
return -;
}