exBSGS
<pre><code class="language-cpp">#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
namespace Hash{
struct Line{int u, v, next;}e[1000000];
const int HashMod=100007;
int h[HashMod], cnt;
inline void Add(int u, int v, int w){e[++cnt] = (Line){w, v, h[u]}; h[u] = cnt;}
inline void clear(){memset(h, 0, sizeof(h)); cnt = 0;}
inline void insert(int x, int k = 0){
int s = x % HashMod;
Add(s, k, x);
}
inline int query(int x){
int s = x % HashMod;
for(int i = h[s]; i; i = e[i].next)
if(e[i].u == x) return e[i].v;
return 0;
}
inline int count(int x){
int s = x % HashMod;
for(int i = h[s]; i; i = e[i].next)
if(e[i].u == x) return 1;
return 0;
}
}
namespace BSGS{
const int m = 1000;
int ff, yy;
inline ll qpow(ll a, ll b, ll p){
int sum = 1;
while(b){
if(b & 1) sum = sum * a % p;
a = a * a % p;
b >>= 1;
}
return sum;
}
inline void pre_bsgs(int a, int p) {
Hash::clear();
int f = 1, y = ceil(1.0 * p / m);//这里m对应着用y复杂度预处理，m复杂度处理每次询问。
ff = qpow(a, y, p); yy = y;
for(int i = 0; i < y; i++) {
Hash::insert(f, i);
f = 1LL * f * a % p;
}
}
inline int bsgs(int a, int b, int p) {
if(b == 1) return 0;
int f = ff, y = yy, tmp = f;
// 仿照上面的第二种思路，f变成a^y*ni(b)并赋值给tmp
f = 1LL * f * qpow(b, p-2, p) % p;
for(int i = 1; i <= m; i++) {//这里用m复杂度处理询问
if(Hash::count(f)) return i * y - Hash::query(f);
f = 1LL * f * tmp % p;
}
return -1;
}
inline int ex_BSGS(int y, int z, int p){
if(z == 1) return 0;
int k = 0, a = 1;
while(233){
int d = __gcd(y,p);
if(d == 1) break;
if(z % d) return -1;
z /= d; p /= d; ++k; a = 1ll*a*y/d % p;
if(z == a) return k;
}
Hash::clear();
int m = sqrt(p) + 1;
for(int i = 0, t = z; i < m; ++i, t = 1ll*t*y%p) Hash::insert(t, i);
for(int i = 1, tt = qpow(y, m, p), t = 1ll*a*tt % p; i <= m; ++i, t = 1ll*t*tt%p){
int B = Hash::count(t);
if(B == 0) continue;
B = Hash::query(t);
return i * m - B + k;
}
return -1;
}
}</code></pre>