用于求解 $A^x=B(mod C)$ 这样的方程

当A与C互质时，令 $x=im+j$ , 原式可化为 $A^j=B\cdot A^{-mi}(mod C)$ ，然后循环遍历j，并把 $(A^{j}\%C,j)$ 加入哈希表中，然后枚举左边 $B\cdot A^{-mi}\%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 != -1; i = next[i])
        if(hs[i] == x)
            return id[i];
    return -1;
}
int BSGS(int a,int b,int c)
{
    memset(head, -1, sizeof(head));
    top = 1;
    if(b == 1)
        return 0;
    int m = sqrt(c*1.0), j;
    long long x = 1, p = 1;
    for(int i = 0; i < m; ++i, p = p*a%c)
        insert(p*b%c, i);
    for(long long i = m; ;i += m)
    {
        if( (j = find(x = x*p%c)) != -1 )
            return i-j;  //a^(ms-j)=b(mod c)
        if(i > c)
            break;
    }
    return -1;
}