poj 2417 Discrete Logging

 這是個求離散對數的問題。以前學密碼學基礎的時候也接觸過，但是沒想到acm裡面還會有這樣的習題。
   問題的意思是給定素數P，給出方程a^x = b % p，注意有模的方程等式2邊都是取模數的意思。解這樣的方程有一個固定的算法，
叫做baby-step算法。但是，注意限定條件是p必須是素數。
   下面的圖描述了這個算法：

   意思很清楚，就是假設x = i * m + j，那麼方程可以轉化為b*(a^-m)^i  = a^j % p。先計算出右邊的值，存儲在一張表裡面，
然後從小到大枚舉左邊的i（0<=i<m)，率先滿足等式的就是最小的解x。
   poj上面這個題用map存儲(a^j,j)對的時候會超時，改成hash表存儲才能過，額，畢竟理論復雜度不是一個數量級的。我的hash表是
開了2個數組，一個鍵，一個值，又來相互驗證，槽沖突的話，一直往後找位置。感覺這樣的做法沒有鏈式hash復雜度平均的樣子。
   代碼如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

#define MAX (1000000)
long long nData[MAX];
long long nKey[MAX];
long long egcd(long long a, long long b, long long& x, long long& y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long ret = egcd(b, a % b, x, y);
    long long t = x;
    x = y;
    y = t - (a / b) * y;
    return ret;
}

long long GetPos(long long key)
{
     return (key ^ 0xA5A5A5A5) % MAX;
}

void Add(long long key, long long data)
{
    long long nPos = GetPos(key);
    while (nData[nPos] != -1)
    {
        nPos = (nPos + 1) % MAX;
    }
    nData[nPos] = data;
    nKey[nPos] = key;
}

int Query(int key)
{
    int nPos = GetPos(key);
   
    while (nData[nPos] != -1)
    {
        if (nKey[nPos] == key)
        {
            return nData[nPos];
        }
        nPos = (nPos + 1) % MAX;
    }
    return -1;
}

long long BabyStep(long long nA, long long nB, long long nP)
{
    long long nM = ceil(sqrt((double)(nP - 1)));
    long long x, y;
    egcd(nP, nA, x, y);//y是nA%p的乘法逆
    y = (y + nP) % nP;
    long long nTemp = 1;
    long long c = 1;//c是nA的—m次
    memset(nData, -1, sizeof(nData));
    memset(nKey, -1, sizeof(nKey));
    for (long long j = 0; j < nM; ++j)
    {
        Add(nTemp, j);
        nTemp = (nTemp * nA) % nP;
        c = (c * y) % nP;
    }
   
    long long r = nB;
    for (int i = 0; i < nM; ++i)
    {
        long long j = Query(r);
        if (j != -1)
        {
            return i * nM + j;
        }
        r = (r * c) % nP;
    }
    return -1;
}

int main()
{
    long long nP, nB, nN;
   
    while (scanf("%I64d%I64d%I64d", &nP, &nB, &nN) == 3)
    {
        long long nAns = BabyStep(nB, nN, nP);
        if (nAns == -1)printf("no solution\n");
        else printf("%I64d\n", nAns);
    }
   
    return 0;
}