[poj2417]Discrete Logging_BSGS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> 
#include <map>
using namespace std;
typedef long long ll;
ll a,b,c,m,f[10000000];
map<ll,int> mp;
ll quick_power(ll x)
{
	ll sum=1;
	ll mid=a;
	while(x)
	{
		if(x&1) sum=sum*mid%c;
		x>>=1;
		mid=(mid*mid)%c;
	}
	return sum;
}
int main()
{
	mp.clear();
	while(scanf("%I64d%I64d%I64d",&c,&a,&b)!=EOF)
	{
		mp.clear();
		if(a%c==0) //判断a,c 是否互质，因为c 是质数，所以直接判断是否整除即可
		{
			printf("no solution\n");
			continue;
		}
		int p=false;
		float akkk=(float)c;
		m=ceil(sqrt(akkk));
		ll ans=b%c;
		mp[ans]=0;
		for(int i=1;i<=m;i++)//拔山过程(Baby-Step)
		{
			ans=(ans*a)%c;
			mp[ans]=i;
		}
		ll t=quick_power(m); ans=1;
		for (int i=1;i<=m;i++)//盖世过程(Giant-Step)
		{
			ans=(ans*t)%c;
			if (mp[ans])
			{
				int t=i*m-mp[ans];
				printf("%I64d\n",(t%c+c)%c);
				p=true;
				break;
			}
		}
		if (!p) 
		printf("no solution\n");
	}
}