【BZOJ3239】Discrete Logging

  Baby Step-Gaint Step随便搞搞就好了。

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn=100010;

LL Pow(LL x,int pow,int p) {LL res=1;for (;pow;(x*=x)%=p,pow>>=1) if (pow&1) (res*=x)%=p;return res;}

int p,b,n,m;
map <int,int> M;

int main()
{
	while (scanf("%d%d%d",&p,&b,&n)==3)
	{
		M.clear();
		m=sqrt(p)+1;
		LL now=n,xx=Pow(b,p-2,p);
		for (int i=1;i<=m;i++)
		{
			if (M[now]) break;
			M[now]=i;
			(now*=xx)%=p;
		}
		now=1,xx=Pow(b,m,p);
		int flag=0;
		for (int i=0;i<m;i++)
		{
			if (M[now]) {printf("%d\n",i*m+M[now]-1);flag=1;break;}
			(now*=xx)%=p;
		}
		if (!flag) printf("no solution\n");
	}
	return 0;
}