1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <map> 5 typedef long long LL; 6 int mul_mod(int a,int b,int n){ // a、b都小于n 7     return a * b % n; 8 } 9 int pow_mod(int a,int p,int n){10     if(p == 0) return 1;11     LL ans = pow_mod(a,p / 2,n);12     ans = ans * ans % n;13     if(p % 2 == 1) ans = ans * a % n;14     return ans;15 }16 // 求x和y使得ax+by=d并且|x|+|y|最小。其中d=gcd(a,b)17 void exgcd(int a,int b,int& d,int& x,int& y){18     if(!b) d = a,x = 1,y = 0;19     else{20         exgcd(b,a % b,d,y,x);21         y -= x * (a / b);22     }23 }24 // 计算模n下a的逆，如果gcd(a,n) != 1，则逆不存在，返回-125 int inv(int a,int n){26     int d,x,y;27     exgcd(a,n,d,x,y);28     return d == 1 ? (x + n) % n : -1;29 }30 // 求解模方程a^x=b(mod n)。n为素数，无解时返回-1.31 int log_mod(int a,int b,int n){32     int m,v,e = 1,i;33     m = (int)sqrt(n + 0.5);34     v = inv(pow_mod(a,m,n),n); // a^m的逆v=a^(-m)35     std::map<int,int> x; // x[j]表示满足ei(=a^i)=j的最小的i36     x[1] = 0;37     for(int i = 1 ; i < m ; i++){ // 计算ei38         e = mul_mod(e,a,n);39         if(!x.count(e)) x[e] = i;40     }41     // 考虑a^(im)、a^(im+1)、...、a^(im+m-1)42     for(int i = 0 ; i < m ; i++){43         if(x.count(b)) return i * m + x[b];44         b = mul_mod(b,v,n);45     }46     return -1;47 }48 int main(){49     printf("%d\n",log_mod(3,4,5));50     return 0;51 }