BSGS

(感觉这东西还是要写一下)

BSGS主要用于求解形如$x^k=y\pmod p$(注意这里p与x互质)这样的方程的最小正整数解的问题

设$m=\lceil\sqrt p\rceil,k=am-b,a\in[1,m],b\in[0,m)$

那么上面的方程可以变形成$x^{am}=yx^b\pmod p$

枚举$b$,计算出右边的值存到$map$中,枚举$a$查表即可

Q:可以枚举左边存表,右边查嘛?

A:可以,但是左边查到表可以直接输出...

顺便一说,map里要存最大值,这样你算出的答案是最小的,所以能更新就更新

复杂度:$O(\sqrt plogp)$

模板题[TJOI2007]可爱的质数

#include<bits/stdc++.h>

using namespace std;

int p;

map<int,int>M;

int ksm(int x,int y){

    int s=1;

    while(y){if(y&1)s=1ll*s*x%p;x=1ll*x*x%p;y>>=1;}

    return s;

}

int main(){

    int x,y;

    cin>>p>>x>>y;

    int m=sqrt(p)+1;

    int s=y;

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

        M[s]=i;//能更新就更新

        s=1ll*s*x%p;

    }

    int t=ksm(x,m);s=1;

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

        s=1ll*s*t%p;

        if(M.count(s)){printf("%d\n",i*m-M[s]);return 0;}

    }

    puts("no solution");return 0;

}

扩展BSGS

当p不是素数时(这时x,p不一定互质),

设d=gcd(x,p),

若d不整除y,那么只有y=1时,x=0,其他情况均无解

若d整除y,当d=1时,直接BSGS

否则有$$x^k=y\pmod p$$

\[x^{k-1}×\frac{x}{d}=\frac{y}{d}\pmod{\frac{p}{d}}
\]

继续分解到d=1为止.

\[x^{k-t}×\frac{x^t}{\prod d_i}=\frac{y}{\prod d_i}\pmod{\frac{p}{\prod d_i}}
\]

然后首先检验x=[0,t)是否为解,显然t是log级别的

如果[0,t)都不是解,由于$x,\frac{p}{\prod d_i}$互质,BSGS求解即可

最后记得答案加上t啊

模板题[SPOJ3105]MOD

#include<bits/stdc++.h>

using namespace std;

int re(){

	int x=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*w;

}

int p;

map<int,int>M;

void mul(int&x,int y){x=1ll*x*y%p;}

int ksm(int x,int y){

	int s=1;

	while(y){if(y&1)mul(s,x);mul(x,x);y>>=1;}

	return s;

}

void exbsgs(int x,int y){

	if(y==1){puts("0");return;}

	int d=__gcd(x,p),k=1,t=0;

	while(d^1){

		if(y%d){puts("No Solution");return;}

		++t;y/=d;p/=d;mul(k,x/d);

		if(y==k){printf("%d\n",t);return;}

		d=__gcd(x,p);

	}

	int s=y;M.clear();int m=sqrt(p)+1;

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

		M[s]=i;mul(s,x);

	}

	s=k;k=ksm(x,m);

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

		mul(s,k);

		if(M[s]){printf("%d\n",i*m-M[s]+t);return;}

	}

	puts("No Solution");

}

int main(){

	int x,y;

	while(1){

		x=re(),p=re(),y=re();

		if(!x&&!p&&!y)break;

		x%=p;y%=p;

		exbsgs(x,y);

	}

	return 0;

}

巴特西

[note]BSGS & exBSGS

BSGS

扩展BSGS

最新文章

热门文章