这是个名字很新奇的算法。它用来求方程a^xΞb(mod c)的最小非负整数解，其中ac互质。

　　先看欧拉定理：a^Φ(c)Ξ1(mod c)。所以x肯定在0~Φ(c)-1里面。所以我们可以考虑枚举x。但显然会超时。

　　大步小步算法将我们的暴力枚举变得更加优雅了些。它的步骤是：把0~c-1分成m=√Φ(c)块，然后把a⁰,a¹,a²...a^m mod c存进去。这里有两种思路，一种是hash，另一种是有序数组加二分，差异不大。如果有解，x就可以表示成i*m+j的形式。于是我们枚举i，a^i*m+j=(aⁱ)^m*a^jΞb(mod c)，再分别求出(aⁱ)^m mod c和a^j mod c即可。怎么求呢？(aⁱ)^m容易得到，所以我们来看a^j mod c。

　　　　1.扩展欧几里得。先求出u=(aⁱ)^m，方程就变为a^jΞb/u(mod c)，然后扩欧即可。

　　　　2.欧拉定理。v=a^j mod c=a^Φ(c)-i*m*b mod c，因为ac互质，所以v唯一。

　　显然第二种更简单。求出v之后，我们再去之前的有序数组或者hash表里面查找最小的j使得a^j mod c = v，若找到了答案就为i*m+j，否则无解。

　　时间复杂度为O(clogc)。

　　下面是UVA10225 Discrete Logging的代码。注：题中的c为素数，2≤a,b≤c-1，2≤c≤2^31-1所求方程为a^xΞb(mod c)

#include 
     
      #include 
      
       #include 
       
        #define maxn 1000010using namespace std;pair
        
          re[maxn];inline long long find(long long l, long long r, long long x){    long long mid;    while(l != r){        mid = (l + r) >> 1;        if(re[mid].first < x) l = mid + 1;        else r = mid;    }    return re[l].first == x ? l : -1;}inline long long pow(long long a, long long b, long long c){    long long ans = 1;    while(b){        if(b & 1) ans = (long long) ans * a % c;        a = (long long) a * a % c;        b >>= 1;    }    return ans;}inline long long solve(long long a, long long b, long long c){    long long m = (double)(sqrt(c - 1) + 0.5);    re[0].second = 0, re[0].first = 1;    for(long long i = 1; i < m; i++)        re[i].second = i, re[i].first = re[i - 1].first * a % c;    sort(re, re + m);    for(long long i = 0; i <= m; i++){        long long v = (long long)pow(a, c - 1 - i * m, c) * b % c;        long long j = find(0, m - 1, v);        if(~j) return (long long)i * m + re[j].second;    }    return -1;}int main(){    long long a, b, c;    scanf("%lld %lld %lld", &c, &a, &b);    long long ans = solve(a, b, c);    if(~ans) printf("%lld\n", ans);    else puts("no solution");    return 0;}