[文章目录]
Description
Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 2 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL=N (%p)
BSGS裸题，之前写了个计算器的题一样的。然后，YY了个写hash的过程，将权%一个数，然后挂链，每次寻找的时候扫一遍，感觉还可行。据Po大爷讲，其实可以将i*m+j=x换一种形式，变成aim=b*aj这样就不用求逆元了，当然，p还得是质数。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll b,n;
ll p;
ll mod=1000003,head[1001000],to[101000],nxt[101000],data[101000],z[101000],cnt;
void Hash(ll x,ll val)
{
ll id=x%mod;
to[++cnt]=x;
data[cnt]=val;
nxt[cnt]=head[id];
head[id]=cnt;
z[cnt]=id;
}
ll Find(ll x,ll mx)
{
ll id=x%mod,re=0;
for(ll j=head[id];j;j=nxt[j])
if(to[j]==x&&mx>=data[j]-1) re=max(re,data[j]);
return re;
}
void clear()
{
for(ll i=1;i<=cnt;i++)
head[z[i]]=0;
cnt=0;
}
ll quick_pow(ll x,ll y)
{
ll re=1;
while(y)
{
if(y&1) re=re*x%p;
y>>=1; x=x*x%p;
}
return re;
}
int main()
{
while(~scanf("%lld%lld%lld",&p,&b,&n))
{
clear();
ll m=(int)sqrt(p)+1,now=n;
for(ll i=0;i<m;i++)
Hash(now,i+1),now=now*b%p;
ll inv=quick_pow(b,m); now=1;
bool flag=1;
for(ll j=0;j<p;j+=m)
{
ll y=Find(now%p,j);
if(y)
{
printf("%d\n",j-y+1);
flag=0; break;
}
now=1ll*now*inv%p;
}
if(flag) puts("no solution");
}
return 0;
}