這是個(gè)求離散對(duì)數(shù)的問(wèn)題。以前學(xué)密碼學(xué)基礎(chǔ)的時(shí)候也接觸過(guò)，但是沒(méi)想到acm里面還會(huì)有這樣的習(xí)題。
問(wèn)題的意思是給定素?cái)?shù)P，給出方程a^x = b % p，注意有模的方程等式2邊都是取模數(shù)的意思。解這樣的方程有一個(gè)固定的算法，
叫做baby-step算法。但是，注意限定條件是p必須是素?cái)?shù)。
下面的圖描述了這個(gè)算法：
意思很清楚，就是假設(shè)x = i * m + j，那么方程可以轉(zhuǎn)化為b*(a^-m)^i = a^j % p。先計(jì)算出右邊的值，存儲(chǔ)在一張表里面，
然后從小到大枚舉左邊的i（0<=i<m)，率先滿足等式的就是最小的解x。
poj上面這個(gè)題用map存儲(chǔ)(a^j,j)對(duì)的時(shí)候會(huì)超時(shí)，改成hash表存儲(chǔ)才能過(guò)，額，畢竟理論復(fù)雜度不是一個(gè)數(shù)量級(jí)的。我的hash表是
開(kāi)了2個(gè)數(shù)組，一個(gè)鍵，一個(gè)值，用來(lái)相互驗(yàn)證，槽沖突的話，一直往后找位置。感覺(jué)這樣的做法沒(méi)有鏈?zhǔn)絟ash復(fù)雜度平均的樣子。
代碼如下：
#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;
}