@ 的题解

前置芝士

会取模运算就行啦！

正文部分

拔山盖世 $\tt{BSGS}$ 算法用于求解 $a^x \equiv b \pmod{p}, \ a \perp p$ 中 $x$ 的值。

设 $x = ti - j$，$t = \left \lceil \sqrt{p} \right \rceil$，$1 \le i \le t$，$0 \le j < t$。

然后简单化一下：

$$a^{ti-j} \equiv b \ \ \ \ \Rightarrow \ \ \ \ a^{ti} \equiv ba^j \pmod{p} $$

因为 $ba^j$ 只有 $t$ 个取值，可以先枚举 $j$ ，求出所有的 $ba^j$ 并使用 $\tt{Hash}$ 或 $\tt{map}$ 存储，然后枚举 $i$，求出 $a^{ti}$，查找是否有与之相等的 $ba^j$ ，若有则 $ti-j$ 即为合法的 $x$ 值。不算 $\tt{Hash}$ 或 $\tt{map}$ 的化，复杂度 $\Theta(\sqrt{p})$。

CODE

int Pow(int x, int k, int p, int r = 1) {
	for (; k; k >>= 1, x = x * x % p) {
		if (k & 1) r = r * x % p;
	}
	return r;
}

int bsgs(int a, int b, int p) {
	b %= p, a %= p;
	map<int, int> m;
	int t = ceil(sqrt(p)), k = 1;
	for (int i = 0; i < t; i ++, k = k * a % p) {
		m[k * b % p] = i;
	}
	a = Pow(a, t, p), k = a;
	for (int i = 1; i <= t; i ++, k = k * a % p) {
		if (m.find(k) == m.end()) continue;
		if (i * t - m[k] >= 0) return i * t - m[k];
	}
	return -1;
}

exBSGS

使用 $\tt{BSGS}$ 有一个限制条件，即 $a \perp p$，$\tt{exBSGS}$ 就是为了解决这个问题。

考虑 $a$、$p$ 不互质时怎么做，设 $g = \gcd(a,p)$，$a = a'g$，$p=p'g$，易得 ：

$$a'^xg^x-kp'g=b$$ $$\Rightarrow g \left( a'^x g^{x-1} - kp'\right) = b $$$$\Rightarrow g \mid b$$

得到有解的条件：$g \mid b$。 然后继续瞎搞一波：

$$a^x \equiv b \pmod{p}$$ $$\Rightarrow \dfrac{a^x}{g} \equiv \dfrac{b}{g} \pmod{p'} $$$$\Rightarrow a' \times a^{x -1} \equiv \dfrac{b}{g} \pmod{p'} $$$$\Rightarrow a^{x-1} \equiv \dfrac{b}{g} \times a'^{-1} \pmod{p'} $$

每次使 $b = \dfrac{b}{g} \times a'^{-1}$，$p = p'$，缩小问题范围，一直做到 $a$，$p$ 互质即可 $\tt{BSGS}$ 求解。注意 $a$ 的指数变为 $x-1$。

CODE

int Pow(int x, int k, int p, int r = 1) {
	for (; k; k >>= 1, x = x * x % p) {
		if (k & 1) r = r * x % p;
	}
	return r;
}

void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {x = 1, y = 0; return;};
	exgcd(b, a % b, x, y);
    int t = y; y = x - (a / b) * y, x = t;
}

int Inv(int x, int p, int a = 0, int b = 0) {
	return exgcd(x, p, a, b), (a % p + p) % p;
}

int gcd(int a, int b) {
	return (!b ? a : gcd(b, a % b));
}

int bsgs(int a, int b, int p) {
	b %= p, a %= p;
	map<int, int> m;
	int t = ceil(sqrt(p)), k = 1;
	for (int i = 0; i < t; i ++, k = k * a % p) {
		m[k * b % p] = i;
	}
	a = Pow(a, t, p), k = a;
	for (int i = 1; i <= t; i ++, k = k * a % p) {
		if (m.find(k) == m.end()) continue;
		if (i * t - m[k] >= 0) return i * t - m[k];
	}
	return -1;
}

int exbsgs(int a, int b, int p) {
	b %= p, a %= p;
	if(b == 1 || p == 1)return 0;
	int g = gcd(a, p), s = 0, c = 1;
	for (; g > 1; g = gcd(a, p)) {
		if (b % g != 0) return -1;
		b /= g, p /= g, (c *= a / g) %= p, s ++;
		if (b == c) return s;
	}
	int res = bsgs(a, b * Inv(c, p), p);
	return (~res ? res + s : res);
}

参考：OI Wiki，https://mancityfc.blog.luogu.org/solution-p3846，cqh's blog 。

@ 的题解

扩展 $\textbf{BSGS}$ 算法

这道题是 $\text{exBSGS}$ 的模板题。

先了解一下普通的 扩展 $\text{BSGS}$ 算法。

已知 $a,b,p$，求最小的正整数 $x$ 满足

$$a^x \equiv b\ \mod p$$

其中 $p$ 是质数。

$\text{BSGS}$ 的思想核心是分块

考虑设 $S=\sqrt p$，那么每个 $x$ 都可以表示为 $nS+m$ 的形式。

对于所有 $(0\le k\le S)$，把 $b+a^k$ 放到哈希表（也可以放到 $\text{map}$ ）中。

枚举 $n$ ，然后看是否有满足条件 $m$ 即可。

时间复杂度 $O(\sqrt p)$。

接下来考虑 $\text{exBSGS}$ 问题。

已知 $a,b,p$，求最小的正整数 $x$ 满足

$$a^x \equiv b\ \mod p$$

其中 $p$ 是任意正整数。

考虑将这个问题转化为普通的 $\text{BSGS}$ 问题，即将 $p$ 转化为质数。

设 $D=\gcd(a,p)$ 那么如果 $D\nmid b$ 那显然无解。

原式变成

$$\frac{a^x}{D} \equiv \frac{b}{D}\ \mod \frac{p}{D} $$

取出一个 $a$。

$$a^{x-1}\times \frac{a}{D} \equiv \frac{b}{D}\ \mod \frac{p}{D} $$

可以继续对 $a^{x-1}$ 进行这样的操作，直到 $D=1$。

得到

$$a^{x-k}\times \frac{a^k}{\prod_{i=1}^k d_i} \equiv \frac{b}{\prod_{i=1}^k d_i}\ \mod \frac{p}{\prod_{i=1}^k d_i} $$

此时 $p$ 与 $a$ 互质，直接跑普通的 $\text{BSGS}$ 就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int> mp;
int kuai(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
    return ans;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exBSGS(int a,int b,int p){
    a%=p,b%=p;
    mp.clear();
    if(b==1){
        puts("0");
        return;
    }
    int D=gcd(a,p),sum=1,k=0;
    while(D!=1){
        if(b%D){
            puts("No Solution");
            return;
        }
        b/=D,p/=D;
        k++;
        sum=1ll*sum*(a/D)%p;
        if(sum==b){
            printf("%d\n",k);
            return;
        }
        D=gcd(a,p);
    }
    int now=b;
    int S=ceil(sqrt(p));
    mp[now]=1;
    for(int i=1;i<=S;i++){
        now=1ll*now*a%p;
        mp[now]=i+1;
    }
    now=kuai(a,S,p);
    for(int i=1;i<=S;i++){
        sum=1ll*sum*now%p;
        if(mp.find(sum)!=mp.end()){//注意此处不要直接mp[sum]，容易TLE
            printf("%d\n",i*S-mp[sum]+1+k);
            return;
        }
    }
    puts("No Solution");
}
int a,b,p;
int main() {
    while(scanf("%d%d%d",&a,&p,&b)){
        if(!a&&!b&&!p)break;
        exBSGS(a,b,p);
    }
    return 0;
}

@ 的题解

注：标点符号已补上

1.BSGS(大步小步算法)

EXBSGS 在下面，会 BSGS 可以直接跳过。

主要用于求解形如 $a^x\equiv b\pmod q$ 的问题（$a,b,p$ 已知，$p$ 为质数，求 $x$）。

解法

既然叫大步小步，那肯定和大步小步有关（瞎扯）。

简单来说就是一种类似分块的方法。

我们发现答案一定在 $0\sim p-1$ 之间，因为 $a^{p-1}\equiv 1\pmod p$，即 $p-1$ 为一循环节。

于是，我们把 $x$ 在 $0\sim p-1$ 之间方程 $t=\left\lceil\sqrt{p}\right\rceil$ 块，每块大小为 $t$，多出来的部分不用管它，因为超出了循环节，后面出现的数前面一定会出现。

对于每个 $x=0\sim p-1$，$a^x$ 都可以表示为 $a^{i\cdot t-j}$，$i$ 为 $x$ 所在块的编号，$j$ 为 $x$ 在它的块中的倒序排序。可推得：

$$a^{i\cdot t-j}\equiv b\pmod p\Rightarrow a^{i\cdot t}\equiv b\cdot a^j\pmod p $$

可以用一个 hash 数组存起来每一个 $b\cdot a^j$ 对应的 $j$。

然后我们依次枚举每一个块，如果答案在这个块中，计算出 $a^{i\cdot t}=a^{(i-1)t}\cdot a^t$ ，前面的为上个块的数，后面的是一个定值，可以预处理出来。

如果在 hash 数组中找到，就找到了答案；如果所有块都做完，还没找到答案则无解。

算法流程

1. 计算第一个区间中 $b\cdot a^j$ 对应的 $j$，可以用 hash 或 map 来实现。
2. 令 $tmp=a^t$。
3. 枚举每个区间，计算出 $a^{i\cdot t}$，判断是否在这个区间中。
4. 如果答案在这个区间中，直接返回答案。
5. 找完所有块还找不到答案说明无解。

时间复杂度

当 $t=\sqrt{p}$ 时，时间复杂度最小，为 $O(\sqrt{p})$。

如果用 map 来实现，时间复杂度还要乘上一个 $\log$。

代码

int power(int x, int y, int p) {
	int r=1;
	while (y) {
		if (y&1) r=r*x%p;
		x=x*x%p; y>>=1;
	}
	return r;
}

int bsgs(int a, int b, int p) {
	unordered_map<int, int> f;
	int t=ceil(sqrt(p));
	for (int i=1; i<=t; i++) b=b*a%p, f[b]=i;
	int tmp=power(a, t, p); b=1;
	for (int i=1; i<=t; i++) {
		b=b*tmp%p;
		if (f.count(b)) return i*t-f[b];
	}
	return -1;
}

EXBSGS(扩展大步小步算法)

我们需要求一个最小自然数 $x$，满足 $a^x\equiv b\pmod p$，$p$ 为任意整数。

解法

我们考虑什么时候不能用 BSGS 来求，在以下式子中我们需要两个互为充要条件，则右边的推到左边的需要满足存在 $a^j$ 的逆元，只有当 $a,p$ 互质时才满足条件。

$$a^{i\cdot t-j}\equiv b\pmod p\Longleftrightarrow a^{i\cdot t}\equiv b\cdot a^j\pmod p $$

可以发现，当 $\gcd(a,p)=1$ 时，仍然可做，可以用 exgcd 或欧拉定理求出逆元，直接做 BSGS 即可。

当 $\gcd(a,p) \ne 1$ 时我们把方程转化：$a^x+kp=b$，由裴蜀定理可得，当 $\gcd(a,p)\nmid b$ 时无解。

令 $g=\gcd(a,p)$，两边同时除以 $g$ ，得 $\frac{a}{g}\cdot a^{x-1}+k\cdot\frac{p}{g}=\frac{b}{g}$，即 $\frac{a}{g}\cdot a^{x-1}\equiv\frac{b}{g}\pmod {\frac{p}{g}}$。

每次令 $x=x-1,b=\frac{b}{g}\cdot{(\frac{a}{g})}^{-1},p=\frac{p}{g}$。

不断这样做，直到 $\gcd(a,p)=1$ 为止，再做 BSGS 即可。

因为每次要乘以 $\frac{a}{g}$ 的逆元，比较慢，我们可以先保留着，到最后一起乘，这样并不会影响 $\gcd$ 的值，所以不影响正确性。

代码

int gcd(int a, int b) {
	if (!b) return a;
	return gcd(b, a%b);
}

int power(int x, int y, int p) {
	int r=1;
	while (y) {
		if (y&1) r=r*x%p;
		x=x*x%p; y>>=1;
	}
	return r;
}

void exgcd(int a, int b, int &x, int &y) {
	if (!b) { x=1; y=0; return; }
	exgcd(b, a%b, x, y);
	int t=x; x=y; y=t-a/b*y;
}

int inv(int x, int p) {
	int inv, k;
	exgcd(x, p, inv, k);
	return (inv%p+p)%p;
}

int bsgs(int a, int b, int p) {
	map<int, int> f;
	int t=ceil(sqrt(p));
	for (int i=1; i<=t; i++) b=b*a%p, f[b]=i;
	int tmp=power(a, t, p); b=1;
	for (int i=1; i<=t; i++) {
		b=b*tmp%p;
		if (f.count(b)) return i*t-f[b];
	}
	return -1;
}

int exbsgs(int a, int b, int p) {
	if (b==1 || p==1) return 0;
	int g, tot=0, c=1;
	while ((g=gcd(a, p))>1) {
		if (b%g) return -1;
		b/=g; p/=g; c=c*(a/g)%p; tot++;
		if (b==c) return tot;
	}
	int res=bsgs(a, b*inv(c, p)%p, p);
	if (res==-1) return -1;
	return res+tot;
}