BSGS+exBSGS POJ2417+POJ3243

时间：2022-03-20 20:51:17

a^x=b(mod p）求x,利用分块的思想根号p的复杂度求答案，枚举同余式两端的变量，用hash的方法去找最小的答案（PS：hash看上去很像链式前向星就很有好感）。然后如果p不是质数时，就利用同余式的性质，把(a,p)的最大公约数除掉，然后把残缺的部分用一个d存一下，就可以转化为普通的BSGS了。这里那个在while中的特判b==d要不要我也不确定，加了肯定对。当然一个明确的特判是b==1时这时直接返回答案为0就OK。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<bitset>

#include<set>

#include<cstring>

#include<string>

#define ll long long

#define pb push_back

#define _mp make_pair

#define db double

using namespace std;

const int maxn=100007;

const int maxm=100005;

ll has[maxn];

ll fir[maxn],nxt[maxn],ans[maxn];

int tot;

ll a,b,p;

void add(ll x,ll k)

{

	ll p=x%maxn;

	ans[++tot]=k;nxt[tot]=fir[p];fir[p]=tot;

	has[tot]=x;

}

ll query(ll x)

{

	ll p=x%maxn;

	for(int i=fir[p];i!=-1;i=nxt[i])

	{

		if(has[i]==x)return ans[i];

	}

	return -1;

}

ll bsgs(ll a,ll b,ll p)

{

	if(b==1)return 0ll;

	ll tmp=1,d=1,cnt=0;

	while((tmp=__gcd(a,p))!=1)

	{

		if(b%tmp)return -1;

		b/=tmp;p/=tmp;d=d*(a/tmp)%p;cnt++;

		if(b==d)return cnt;//？？？

	}

	ll m=ceil(sqrt((double)p));

	ll q=1;

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

	{

		add((q*b)%p,i);q=(q*a)%p;

	}

	for(ll i=m;i<=p+m;i+=m)

	{

		d=(d*q)%p;

		ll tt=query(d);

		if(tt!=-1)return i-tt+cnt;

	}

	return -1;

}

int main()

{

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

	{

		if(!p&&!a&&!b)return 0;

		memset(fir,-1,sizeof(fir));

		tot=0;

		ll tt=bsgs(a,b,p);

		if(tt==-1)printf("No Solution\n");

		else printf("%lld\n",tt);

	}

}

　

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<bitset>

#include<set>

#include<cstring>

#include<string>

#define ll long long

#define pb push_back

#define _mp make_pair

#define db double

using namespace std;

const int maxn=1000007;

const int maxm=100005;

ll has[maxn];

int fir[maxn],nxt[maxn],ans[maxn];

int tot;

ll a,b,p;

void add(ll x,int k)

{

	int p=x%maxn;

	ans[++tot]=k;nxt[tot]=fir[p];fir[p]=tot;

	has[tot]=x;

}

int query(ll x)

{

	int p=x%maxn;

	for(int i=fir[p];i!=-1;i=nxt[i])

	{

		if(has[i]==x)return ans[i];

	}

	return -1;

}

ll bsgs(ll a,ll b,ll p)

{

	if(b==1)return 0ll;

	ll m=ceil(sqrt((double)p));

	ll q=1,x=1;

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

	{

		add((q*b)%p,i);q=(q*a)%p;

	}

	x=(x*q)%p;

	for(ll i=m;i<=p;i+=m)

	{

		ll tt=query(x);

		if(tt!=-1)return i-tt;

		x=(x*q)%p;

	}

	return -1;

}

int main()

{

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

	{

		memset(fir,-1,sizeof(fir));

		tot=-1;

		ll tt=bsgs(a,b,p);

		if(tt==-1)printf("no solution\n");

		else printf("%lld\n",tt);

	}

}

　　

　　

相关文章