BSGS
一、简介
BSGS支持形如
$$b^l\equiv n \pmod p$$
在$O(\sqrt p)$的时间复杂度能够求得l的大小
二、前置(没有什么意义)
可以观察到，从$b0$到$bp$中，必有一个数是同余的。去掉$b^p$，会有两种情况
1. $b0$到$b$两两不同
可以得到一定有解
2. otherwise
若$b^i \equiv b^j \pmod p$，则有$b^{i-1} \equiv b^{j-1} \pmod p$，可得一定存在循环节(从$b=0$开始)
二、思想
分块
令$t=\sqrt p$，可以得到从0~p-1中被划分为t块。若存在某个$b^l \equiv n \pmod p$，则令两边同时乘上$b^j$。
即得到$b^{tk} \equiv nb^j \pmod p$
对于任意$bl$，一定存在$b \leq b^l < b^{t \cdot k}$，由此可得上文中的$j$存在$0 \leq j < t$。
对于每一个k，我们可以寻找有没有符合条件的j
由此可得，全局只需要处理第一块区间的所有$n*bi$和每一个区间的边界(即每一个$b，0 \leq k < t$)。
综上，对于整个代码只需要$O(\sqrt p)$，(若使用map需要乘上 $\log \sqrt p$ ，hash则不需要)
三、代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
#define int long long
int qpow(int a, int b, int mod){int res = 1ll;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
int bsgs(int a, int b, int p){map<int, int> hsh; hsh.clear();if(p == 1) return 0;b %= p;if(b == 1) return 0;int t = ceil(sqrt(p));// 首先要求a^x和b模p同余// a^(i*t)和b*a^j模p同余//此处预处理所有的b*a^jfor(int i = 0ll; i < t; i++) hsh[b * qpow(a, i, p) % p] = i; // BS，即处理0~sqrt(p)的a^i // i=1时的a^(i*t) a = qpow(a, t, p);if(!a){if(b == 0ll) return 1ll;return -1;}for(int i = 1; i <= t; i++){//val是不同的(a^t)^iint val = qpow(a, i, p);int j = 0;// 寻找有没有a^(i*t)和某个b*a^j同余 if(hsh.find(val) != hsh.end()) j = hsh[val];else j = -1;// 存在j且存在i*t-jif(j >= 0 && i * t - j >= 0) return i * t - j;}return -1;
}
int p, b, n;
signed main(){cin >> p >> b >> n;int ans = bsgs(b, n, p);if(ans == -1) cout << "no solution\n";else cout << ans << '\n';return 0;
}