BSGS算法

\(Baby Step Giant Step\)算法，即大步小步算法，缩写为\(BSGS\)

拔山盖世算法

它是用来解决这样一类问题

\(y^x = z (mod\ p)\)，给定\(y,z,p>=1\)求解\(x\)

普通的\(BSGS\)只能用来解决\(gcd(y,p)=1\)的情况

设\(x=a*m+b, m=\lceil \sqrt p \rceil, a\in[0,m), b\in[0,m)\)

那么\(y^{a*m}=z*y^{-b} (mod\ p)\)

怎么求解，为了方便，设\(x=a*m-b\)

那么\(y^{a*m}=z*y^b(mod \ p), a\in(0,m+1]\)

直接暴力辣，把右边的\(b\)枚举\([0,m)\)，算出\(z*y^b(mod \ p)\)，哈希存起来

然后左边\(a\)枚举\((0, m+1]\)，算出\(y^{a*m}(mod \ p)\)查表就行了

然后不知道为什么要用\(exgcd\)，只会\(map\)...

代码

[SDOI2011]计算器

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

template <class Int>

IL void Input(RG Int &x){

    RG int z = 1; RG char c = getchar(); x = 0;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    x *= z;

}

IL void None(){

	puts("Orz, I cannot find x!");

}

int p;

IL int Pow(RG ll x, RG ll y){

	RG ll ret = 1;

	for(; y; x = x * x % p, y >>= 1)

		if(y & 1) ret = ret * x % p;

	return ret;

}

map <int, int> pw;

IL void BSGS(RG int x, RG int y){

	pw.clear();

	if(y == 1){

		puts("0");

		return;

	}

	RG int ans = -1, m = sqrt(p) + 1, xx, s = y;

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

		pw[s] = i;

		s = 1LL * s * x % p;

	}

	xx = Pow(x, m), s = 1;

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

		s = 1LL * s * xx % p;

		if(pw.count(s)){

			ans = i * m - pw[s];

			break;

		}

	}

	if(ans < 0) None();

	else printf("%d\n", ans);

}

int T, k, y, z;

int main(RG int argc, RG char* argv[]){

	for(Input(T), Input(k); T; --T){

		Input(y), Input(z), Input(p);

		if(k == 1) printf("%d\n", Pow(y, z));

		else if(k == 2){

			RG int d = (y % p) ? 1 : p;

			if(z % d) None();

			else printf("%lld\n", 1LL * Pow(y, p - 2) * z % p);

		}

		else{

			if(y % p) BSGS(y % p, z % p);

			else None();

		}

	}

    return 0;

}

扩展BSGS

对于\(gcd(y, p)\ne1\)怎么办？

我们把它写成\(y*y^{x-1}+k*p=z, k\in Z\)的形式

根据\(exgcd\)的理论

那么如果\(y,p\)的\(gcd\)不是\(z\)的约数就不会有解

设\(d=gcd(y,p)\)

那么

\[\frac{y}{d}*y^{x-1}+k*\frac{p}{d}=\frac{z}{d}
\]

递归到\(d=1\)

设之间的所有的\(d\)的乘积为\(g\)，递归\(c\)次

令\(x'=x-c, p'=\frac{p}{g},z'=\frac{z}{g}\)

那么

\[y^{x'}*\frac{y^c}{g}=z'(mod \ p')
\]

那么\(BSGS\)求解就好了

代码

SPOJMOD Power Modulo Inverted

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

# define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

using namespace std;

typedef long long ll;

template <class Int>

IL void Input(RG Int &x){

    RG int z = 1; RG char c = getchar(); x = 0;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    x *= z;

}

map <int, int> pw;

IL int Gcd(RG int x, RG int y){

	return !y ? x : Gcd(y, x % y);

}

IL int Pow(RG ll x, RG ll y, RG int p){

	RG ll ret = 1;

	for(; y; x = x * x % p, y >>= 1)

		if(y & 1) ret = ret * x % p;

	return ret;

}

int a, b, p;

IL int EX_BSGS(){

	if(b == 1) return 0;

	pw.clear();

	RG int cnt = 0, t = 1, s, x, m;

	for(RG int d = Gcd(a, p); d != 1; d = Gcd(a, p)){

		if(b % d) return -1;

		++cnt, b /= d, p /= d, t = 1LL * t * a / d % p;

		if(b == t) return cnt;

	}

	s = b, m = sqrt(p) + 1;

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

		pw[s] = i;

		s = 1LL * s * a % p;

	}

	x = Pow(a, m, p), s = t;

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

		s = 1LL * s * x % p;

		if(pw.count(s)) return i * m - pw[s] + cnt;

	}

	return -1;

}

int ans;

int main(RG int argc, RG char* argv[]){

	for(Input(a), Input(p), Input(b); a + b + p;){

		a %= p, b %= p, ans = EX_BSGS();

		if(ans < 0) puts("No Solution");

		else printf("%d\n", ans);

		Input(a), Input(p), Input(b);

	}

    return 0;

}

巴特西

BSGS算法及扩展

BSGS算法

代码

扩展BSGS

代码

最新文章

热门文章