与数论的厮守03：大步小步算法

　　这是个名字很新奇的算法。它用来求方程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 <algorithm>
#include <cstdio>
#include <cmath>
#define maxn 1000010
using namespace std;

pair<int, int> 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;
}