模板：

unordered_map
    
      mp;LL q_pow(LL n, LL k, LL p) {    LL ans = 1;    if(k == -1) return 0;    while(k) {        if(k&1) ans = (ans*n) % p;        n = (n*n) % p;        k >>= 1;    }    return ans;}int BSGS(int a, int b, int p){    int m = sqrt(p)+1, s = b;    mp.clear();    for(int i = 0; i < m; ++i){        mp[s]=i;        s= (s*1LL*a)%p;    }    int t = q_pow(a, m, p);    s = 1;    for(int i = 1; i <= m; ++i){        s = (s*1LL*t)%p;        if(mp.find(s) != mp.end()) return i*m-mp[s];    }    return -1;}int exBSGS(int a, int b, int p) {    int d = __gcd(a, p), k = 1, t = 0;    while(d^1){        if(b%d) return -1;        ++t;        b /= d;        p /= d;        k = (k*1LL*(a/d)) % p;        if(b == k) return t;        d = __gcd(a, p);    }    int s = b;    mp.clear();    int m = sqrt(p) + 1;    for(int i = 0;i < m; ++i){        mp[s] = i;        s = (s*1LL*a) % p;    }    s = k;    k = q_pow(a, m, p);    for(int i = 1; i <= m; ++i){        s = (s*1LL*k) % p;        if(mp.find(s) != mp.end()) return i*m-mp[s]+t;    }    return -1;}
    

例题：

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headunordered_map
          
            mp;LL q_pow(LL n, LL k, LL p) { LL ans = 1; if(k == -1) return 0; while(k) { if(k&1) ans = (ans*n) % p; n = (n*n) % p; k >>= 1; } return ans;}int exBSGS(int a, int b, int p) { int d = __gcd(a, p), k = 1, t = 0; while(d^1){ if(b%d) return -1; ++t; b /= d; p /= d; k = (k*1LL*(a/d)) % p; if(b == k) return t; d = __gcd(a, p); } int s = b; mp.clear(); int m = sqrt(p) + 1; for(int i = 0;i < m; ++i){ mp[s] = i; s = (s*1LL*a) % p; } s = k; k = q_pow(a, m, p); for(int i = 1; i <= m; ++i){ s = (s*1LL*k) % p; if(mp.find(s) != mp.end()) return i*m-mp[s]+t; } return -1;}int a, b, p;int main() { while(~scanf("%d %d %d", &a, &p, &b)) { if(!a && !b && !p) break; if(b == 1) { if(p == 1) printf("No Solution\n"); else printf("0\n"); } else { int x = exBSGS(a, b, p); if(~x) printf("%d\n", x); else printf("No Solution\n"); } } return 0;}