Discrete Logarithm II

ll DiscreteLogarithm (ll a, ll b, ll mod) {
    a %= mod, b %= mod;
    if (b == 1) return 0;
    int cnt = 0; ll t = 1, g;
    while ((g = __gcd (a, mod)) != 1) {
        if (b % g) return -1;
        mod /= g, b /= g;
        t = t * a / g % mod;
        cnt++;
        if (t == b) return cnt;
    }
    unordered_map <ll, ll> mp;
    int m = ceil (sqrt (1.0 * mod));
    ll e = 1;
    for (int i = 0; i < m; i++) {
        mp[e * b % mod] = i;
        e = e * a % mod;
    }
    ll nw = t;
    for (int i = 1; i <= m + 1; i++) {
        nw = e * nw % mod;
        if (mp.count(nw)) {
            return i * m - mp[nw] + cnt;
        }
    }
    return -1;
}