bzoj 3239: Discrete Logging && 2480: Spoj3105 Mod【BSGS】

都是BSGS的板子题

此时 \( 0 \leq x \leq p-1 \)

设 \( m=\left \lceil \sqrt{p} \right \rceil ,x=i*m-j \)这里-的作用是避免逆元

于是可以把式子变形成这样：\( a^{im}\equiv ba^j(mod\ p) \)

枚举右边\( 0 \leq j <m \) ，用map或者hash以模数为下标来存每一个j

枚举左边\( 0 \leq i <m \) ，在map或者hash中查找对应的模数

#include<iostream>

#include<cstdio>

#include<map>

#include<cmath>

using namespace std;

long long a,b,p;

map<long long,long long>mp;

long long ksm(long long a,long long b,long long p)

{

	long long r=1ll;

	a%=p;

	while(b)

	{

		if(b&1)

			r=r*a%p;

		a=a*a%p;

		b>>=1;

	}

	return r;

}

int main()

{

	while(~scanf("%lld%lld%lld",&p,&a,&b))

	{

		a%=p;

		if(!a&&!b)

		{

			puts("1");

			continue;

		}

		if(!a)

		{

			puts("no solution");

			continue;

		}

		if(b==1)

		{

			puts("0");

			continue;

		}

		mp.clear();

		int m=ceil(sqrt(p)),t=b,f=0;

		for(int i=0;i<m;i++)

		{

			mp[t]=i;

			t=(long long)t*a%p;

		}

		int g=ksm(a,m,p);

		t=(long long)g%p;

		for(int i=1;i<=m+1;i++)

		{

			if(mp.count(t))

			{

				f=1;

				printf("%lld\n",i*m-mp[t]);

				break;

			}

			t=(long long)t*g%p;

		}

		if(!f)

			puts("no solution");

	}

	return 0;

}

巴特西

bzoj 3239: Discrete Logging && 2480: Spoj3105 Mod【BSGS】

最新文章

热门文章