exBSGS

#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;
    }
}