BZOJ 3239 Discrete Logging

题目大意

求最小的$x$满足$a^x \equiv b (\text{mod }c)$

$a,b,c \le 10^9$, $c$为质数。

普通BSGS模板题，具体请看学习笔记。

我当时还不是很了这个算法，所以写的和笔记描述的不一致。与笔记一致的题解

#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,b,c;
map<ll,ll>mp;
ll qpow(ll x,ll y)
{
	ll ret=1;
	while(y)
	{
		if(y&1) ret=ret*x%c;
		x=x*x%c,y>>=1;
	}
	return ret;
}
void calc()
{
	mp.clear();
	ll m=ceil(sqrt(c)),i,t,u=qpow(a,c-m-1);
	map<ll,ll>::iterator it;
	for(i=0,t=1;i<m;++i,t=t*a%c) if(mp.find(t)==mp.end()) mp[t]=i;
	for(i=0,t=1;i<m;++i,t=t*u%c)
	{
		it=mp.find(b*t%c);
		if(it!=mp.end())
		{
			printf("%lld\n",i*m+it->second);
			return;
		}
	}
	puts("no solution");
	return;
}
int main()
{
	while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF) calc();
	return 0;
}