Yurchiu's Blog
Yurchiu
An AFO whker.
  首页
  归档
158
  标签
81
  分类
24
  说说
  关于
  留言
  链接
  设置

BSGS 与 exBSGS

Yurchiu 2022-02-02, 23:04:48 2.1k 隐藏左右两栏 展示左右两栏
首页 / BSGS 与 exBSGS

Baby-Step-Giant-Step（大步小步法，北上广深，不是个事，拔山盖世），简称 BSGS，使用分块思想解决离散对数问题。

形如 ab≡c(modm)a^b \equiv c \pmod m 的同余式，可产生以下三种问题：

  1. 已知 a,ba,b ，求 cc，是快速幂问题。
  2. 已知 a,ca,c，求 bb，是离散对数问题。
  3. 已知 b,cb,c，求 aa，是高次剩余问题。

我们现在可以利用扩欧和快速幂解决问题 1；而利用 BSGS 和 exBSGS，我们也可以解决问题 2 了！

BSGS

BSGS 求解 ax≡b(modm)a^x\equiv b\pmod m 中 xx 的值。要求 (a,m)=1(a,m)=1。

下面的代码时间复杂度为 O(mlog⁡m)O(\sqrt{m}\log m)。

//https://www.luogu.com.cn/problem/P3846
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll p,b,n,siz,cnt;
	map<ll,ll>check;
	ll BSGS(ll a,ll c,ll p)
	{
		ll tmp=c%p,jud=1;
		for(ll i=0;i<siz;i++)
		{
			check[tmp]=i;
			tmp=a*tmp%p; jud=jud*a%p;
		}
		tmp=jud;
		for(ll i=1;i<=cnt;i++)
		{
			if(check.count(jud)) return i*siz-check[jud];
			jud=jud*tmp%p;
		}
		return -1;
	}
	void main()
	{
		ll tmp;
		scanf("%lld%lld%lld",&p,&b,&n);
		siz=sqrt(p-1); cnt=((p-1)/siz+((p-1)%siz?1:0));
		tmp=BSGS(b,n,p);
		if(tmp==-1) printf("no solution\n");
		else printf("%lld\n",tmp);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
a^b = c (mod p)
a^{m*siz-k} = c (mod p)
a^{m*siz} = c*a^k (mod p)

(k: 0 ~ size-1)
*/

exBSGS

exBSGS 也是用于求解 ax≡b(modp)a^x\equiv b\pmod p 中 xx 的值。不要求 (a,p)=1(a,p)=1。

显然，若 p=1p=1，一个可行的解为 x=0x=0。

若 p>1p>1，而 b=1b=1，一个可行的解为 x=0x=0。（注意特判）

无解的充分条件是：(a,p)(a,p) 不是 bb 的约数，且 b≠1b\not=1。

证明

若 (a,p)=d>1(a,p)=d>1，则令 a=md,p=nda=md,p=nd。

则有

(md)x≡b(modnd)mxdx−b=kndmxdx−1d−knd=b\begin{aligned} (md)^x&\equiv b\pmod {nd}\\\\ m^xd^x-b&=knd\\\\ m^xd^{x-1}d-knd&=b \end{aligned}

根据裴蜀定理，将 mxdx−1m^xd^{x-1} 和 kk 看作未知数，显然 b=1b=1 或 d∣bd\mid b，上面的不定方程有解，原方程（ax≡b(modp)a^x\equiv b\pmod p）有可能有解。

所以原方程可写成：

adax−1≡bd(modpd)\dfrac{a}{d}a^{x-1}\equiv \dfrac{b}{d}\pmod {\dfrac{p}{d}}

反复迭代，最终得到 a′ax−i≡b′(modp′)a'a^{x-i}\equiv b'\pmod {p'}，其中 (a,p′)=1(a,p')=1。显然 a′a' 存在逆元，BSGS 可求。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll a,b,p;
	map<ll,ll>check;
	ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	void exgcd(ll a,ll b,ll &x,ll &y)
	{
		if(b==0)
		{
			x=1; y=0;
			return;
		}
		exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y; y=tmp-(a/b)*y;
	}
	ll inv(ll a,ll b)
	{
		ll x,y;
		exgcd(a,b,x,y);
		return (x%b+b)%b;
	}
	ll BSGS(ll f,ll a,ll b,ll p,ll c)
	{
		ll siz,cnt,t1,t2=1;
		t1=b=b*inv(f,p)%p; siz=sqrt(p-1);
		if(p==1||b==1) return c;
		cnt=(p-1)/siz+((p-1)%siz?1:0);
		for(ll i=0;i<siz;i++)
		{
			check[t1]=i;
			t1=t1*a%p; t2=t2*a%p;
		}
		t1=t2;
		for(ll i=1;i<=cnt;i++)
		{
			if(check.count(t1)) return siz*i-check[t1]+c;
			t1=t1*t2%p;
		}
		return -1;
	}
	ll exBSGS(ll f,ll a,ll b,ll p,ll step)
	{
		ll d=gcd(a,p);
		if(d==1) return BSGS(f,a,b,p,step);
		if(f%p==b%p) return step;
		if(b%d) return -1;
		return exBSGS(a/d*f%p,a,b/d,p/d,step+1);
	}
	void main()
	{
		ll tmp;
		while(true)
		{
			scanf("%lld%lld%lld",&a,&p,&b);
			if(a==0&&b==0&&p==0) return;
			check.clear();
			
			a%=p; b%=p;
			if(p==1 || (p!=1&&b==1))
			{
				printf("0\n");
				continue;
			}
			
			tmp=exBSGS(1,a,b,p,0);
			if(tmp==-1) printf("No Solution\n");
			else printf("%lld\n",tmp);
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

例题

  • P2485 [SDOI2011]计算器。显然是 sb 三合一。

    #include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll y,z,p;
	map<ll,ll>check;
	ll pow(ll a,ll b,ll p)
	{
		ll ret=1;
		while(b)
		{
			if(b%2) ret=ret*a%p;
			a=a*a%p; b/=2;
		}
		return ret;
	}
	void exgcd(ll a,ll b,ll &x,ll &y)
	{
		if(b==0)
		{
			x=1; y=0;
			return;
		}
		exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y; y=tmp-(a/b)*y;
	}
	ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	void solve()
	{
		ll x,q,d=gcd(y,p);
		if(z%d)
		{
			printf("Orz, I cannot find x!\n");
			return;
		}
		exgcd(y,p,x,q);
		printf("%lld\n",(x%p+p)%p*(z/d)%p);
		return;
	}
	void BSGS(ll a,ll b,ll p)
	{
		ll siz=sqrt(p),t1=b%p,t2=1;
		ll cnt=p/siz+(p%siz?1:0);
		if(t1==1)
		{
			printf("0\n");
			return;
		}
		if(a%p==0&&t1==0)
		{
			printf("1\n");
			return;
		}
		if(a%p==0&&t1)
		{
			printf("Orz, I cannot find x!\n");
			return;
		}
		check.clear();
		for(ll i=0;i<siz;i++)
		{
			check[t1]=i;
			t1=t1*a%p; t2=t2*a%p;
		}
		t1=t2;
		for(ll i=1;i<=cnt;i++)
		{
			if(check.count(t1))
			{
				printf("%lld\n",i*siz-check[t1]);
				return;
			}
			t1=t1*t2%p;
		}
		printf("Orz, I cannot find x!\n");
		return;
	}
	void main()
	{
		ll T,k;
		scanf("%lld%lld",&T,&k);
		while(T--)
		{
			scanf("%lld%lld%lld",&y,&z,&p);
			if(k==1) printf("%lld\n",pow(y,z,p));
			else if(k==2) solve();
			else BSGS(y,z,p);
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

  • P3306 [SDOI2013] 随机数生成器。推推式子。

    #include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll p,a,b,x1,t;
	map<ll,ll>check;
	ll pow(ll a,ll b)
	{
		ll ret=1; a%=p;
		while(b)
		{
			if(b%2) ret=ret*a%p;
			a=a*a%p; b/=2;
		}
		return ret;
	}
	ll inv(ll a){return pow(a,p-2);}
	void exgcd(ll a,ll b,ll &x,ll &y)
	{
		if(b==0)
		{
			x=1; y=0;
			return;
		}
		exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y; y=tmp-(a/b)*y;
	}
	ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	void BSGS(ll a,ll b,ll p)
	{
		ll siz=sqrt(p),t1=b%p,t2=1;
		ll cnt=p/siz+(p%siz?1:0);
		check.clear();
		for(ll i=0;i<siz;i++)
		{
			check[t1]=i;
			t1=t1*a%p; t2=t2*a%p;
		}
		t1=t2;
		for(ll i=1;i<=cnt;i++)
		{
			if(check.count(t1))
			{
				printf("%lld\n",i*siz-check[t1]+1);
				return;
			}
			t1=t1*t2%p;
		}
		printf("-1\n");
		return;
	}
	void main()
	{
		ll T,tmp,t1,t2;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
			if(x1==t) printf("1\n");
			else if(a==0)
			{
				if(b==t) printf("2\n");
				else printf("-1\n");
			}
			else if(a==1)
			{
				if(b==0)
				{
					if(x1==t) printf("1\n");
					else printf("-1\n");
				}
				else
				{
					tmp=gcd(b,p);
					if((t-x1+b)%tmp) {printf("-1\n");continue;}
					exgcd(b,p,t1,t2);
					tmp=(t1*(t-x1+b)/tmp%p+p)%p;
					printf("%lld\n",tmp?tmp:p);
				}
			}
			else if((x1*(a-1)+b)%p==0)
			{
				if((t*(a-1)+b)%p==0) printf("1\n");
				else printf("-1\n");
			}
			else BSGS(a,(t*(a-1)+b)%p*inv(x1*(a-1)+b)%p,p);//取模要彻底啊亲
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/* DBSL
Sn = a+ap+...+ap^n
pSn = ap+ap^2+...+ap^{n+1}
    = Sn+ap^{n+1}-a
Sn=(ap^{n+1}-a)/(p-1)
*/

/* a=0
x2 = b
x3 = b
xi = b
*/

/* a=1,b=0
x2 = x
xi = x
*/

/* a=1,b!=0
x2 = x+b
x3 = x+2b
xi = x+(i-1)b

t = x+(i-1)b (mod p)
t = x+ib-b+kp
ib+kp = t-x+b
*/

/* x(a-1)+b = 0 (mod p)

t(a-1)+b = 0 (mod p)

*/

/* normal
x2 = ax+b
x3 = a(ax+b)+b
   = a^2x+ab+b
x4 = a(a^2x+ab+b)+b
   = a^3x+a^2b+ab+b
x5 = a(a^3x+a^2b+ab+b)+b
   = a^4x+a^3b+a^2b+ab+b
xi = a^{i-1}x + /prod_{j=0}^{i-2}a^jb
   = a^{i-1}x + (a^{i-1}b-b)/(a-1)
   = a^{i-1}x + a^{i-1}b/(a-1) - b/(a-1)
   = a^{i-1}[x+b/(a-1)] - b/(a-1)
a^{i-1} = [t+b/(a-1)]*[x+b/(a-1)]^{-1} (mod p)
a^{i-1} = [t(a-1)+b]*[x(a-1)+b]^{-1} (mod p)
*/



本文作者：Yurchiu

本文链接：https://yz-hs.github.io/2ab979d324b5/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。


OI 数论
最后更新：2023-08-21, 23:18:20
By Yurchiu.
最近更新旧文更新
[Works] 自白 终章
《幽默报 10》
AFO 有感
OI 之旅
《幽默报》
[Works] 自白
[Idea] 试卷排序
其他物件杂物收纳
Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.