模板——大步小步算法

//求解模方程 a^x = b(mod n)  n为素数，无解返回-1
int log_mod(int a, int b, int n) {
    int m, v, e = 1, i;
    m = (int) sqrt(n+0.5);
    v = inv(pow_mod(a, m, n), n);
    map<int, int> x;
    x[1] = 0;
    for(int i = 1; i < m; i++) {
            e = e*a%n;
            if(!x.count(e)) x[e] = i;        
    }  
    for(i = 0; i < m; i++) {
        if(x.count(b)) return i*m + x[b];
        b = b*v%n;   
    }    
    return -1;
}