image.png
    image.png

    1. int exbsgs(int a,int b,int p)
    2. {
    3.     int tot = 1,cnt = 0,d = gcd(a,p);
    4.     b %= p;                   //防止超时 
    5.     if (b==1) 
    6.         return 0;
    7.     while (d>1)//直到gcd(a,p)==1 
    8.     {
    9.         if (b%d)   //b不能被d整除，则无解 
    10.             return -1;
    11.         b /= d;
    12.         p /= d;
    13.         tot *= (a/d);
    14.         tot %= p;
    15.         cnt++;
    16.         if (tot==b) 
    17.             return cnt;
    18.         d = gcd(a,p);
    19.     }
    20.     int x = ex_inv(tot,p);
    21.     b*=x;
    22.     b%=p;
    23.     int res = bsgs(a,b,p);
    24.     if(~res)
    25.         return res+cnt;
    26.     return res;
    27. }