hdu2815 扩展Baby step,Giant step入门

题意：求满足a^x=b(mod n)的最小的整数x。

分析：很多地方写到n是素数的时候可以用Baby step,Giant step, 其实研究过Baby step,Giant step算法以后，你会发现 它能解决 “n与a互质”的情况，而并不是单纯的n是素数的情况。如果a与n不是互质的，那么我们需要处理一下原方程，让a与n互质，然后再用Baby step,Giant step解出x即可。

Baby step,Giant step算法思想：对于a与n互质，那么则有a^phi(n)=1(mod n), 对于n是素数phi(n) == n-1, 否则phi(n) < n-1, 所以x的取值只要在0----n-2之中取就可以了。

当n很小时，可以直接枚举，但当n很大时，肯定会超时，Baby step,Giant step就是用了一种O(sqrt(n)*log(n))的方法枚举了所有的0-----n-2。令m = sqrt(n);

我们可以预处理出a^0,a^1,.........a^m,都放入哈希表中, 然后 (a^m)^i+v(哈希表里的其中一个值)就一定是解，每次枚举i(0-----m-1),计算出v,判断v是否出现在哈希表中，如果有就是解。 对于m为什么取sqrt(n)是为了复杂度的平衡，这一点是跟分块算法很相似的。

对于a与n不互质的情况分析：令 t = gcd(a,n)，那么a与n都约去t，当然b也要约去t(不能约去就无解)，约去一个t以后方程就变为 aa*a^(x-1) = bb(mod nn), (其中 aa = a/t bb = b/t nn = n/t) , 这里nn还可能与a不互质，那么我们一直拿出一个新的a对(a, bb, nn)约去t，直到a与nnn....(nnn...表示约去若干次t以后的n)互质。以下用(用三个字母表示约去若干次后,如bbb) 则结果为aa^c*a^(x-c) = bbb(mod nnn), 我们让等式左右分别乘以aa^c关于nnn的逆元 变为a^(x-c) = w (mod nnn) , w =bbb *(aa^c)^(-1)。 a^x = w (mod n)可以用bbb *(aa^c)^(-1)Baby step,Giant step直接求出，如果有解那把未知数+c。

具体看代码中的cal函数。

注意：在以上过程中x有可能<c，所以我们必须每约去一个t就要特判一下当前情况aa 与 bb就说明当前c是解。

哈希表实现看题目时间要求，map太慢，自己手写hash是很快的。

map哈希

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <map>using namespace std;typedef long long ll;const int maxn = 100007;struct hash {int n;struct Edge {int p, v;int next;}edge[maxn*7];int head[maxn+10], E;void init(int n) {this->n = n;memset(head, -1, sizeof(int)*(n+1));}void add(int p, int v) {int s = p%n;edge[E].p = p;edge[E].v = v;edge[E].next = head[s];head[s] = E++;}int get(int p) {int s = p%n;for(int i = head[s]; ~i; i = edge[i].next) {if(edge[i].p == p) return edge[i].v;}return -1;}}f;void ex_gcd(ll a, ll b, ll &x, ll &y) {    if (!b) {        x = 1;        y = 0;    } else {        ex_gcd(b, a % b, y, x);        y -= a / b * x;    }}inline ll inv(ll a, ll n) {    ll x, y;    ex_gcd(a, n, x, y);    if(x < 0) x += n;    return x;}ll log_mod(ll a, ll b, ll n) {    ll m, e;    int i;    m = sqrt(n + 0.5);    f.init(10007);    f.add(1, 0);    e = 1;    for (i = 1; i < m; i++) {        e = e * a % n;        if (f.get(e) == -1) f.add(e, i);    }    e = e * a % n;    e = inv(e, n);    for (i = 0; i < m; i++) {    int t = f.get(b);        if (~t)            return i * m + t;        b = b * e % n;    }    return -1;}ll gcd(ll a, ll b) {    return b ? gcd(b, a % b) : a;}ll cal(ll a, ll b, ll n) { //扩展函数    ll t, c = 0, v = 1;    while ((t = gcd(a, n)) != 1) {        if (b % t)            return -1;        n /= t;        b /= t;        v = v * a / t % n;        c++;        if (b == v) return c;    }    b = b*inv(v, n)%n;    ll ret = log_mod(a, b, n);    return ~ret ? ret + c : ret;}int a, b, n;int main() {    while (~scanf("%d%d%d", &a, &n, &b)) {        if (b >= n) {            printf("Orz,I can’t find D!\n");            continue;        }        if (b == 0) {            printf("0\n");            continue;        }        ll ans = cal(a, b, n);        if (ans == -1)            printf("Orz,I can’t find D!\n");        else            printf("%I64d\n", ans);    }    return 0;}