「學習筆記」BSGS
點擊查看目錄
目錄
- 「學習筆記」BSGS
- Baby-step Giant-step
- 問題
- 演算法
- 例題
- Discrete Logging
- 代碼
- P3306 [SDOI2013] 亂數生成器
- 思路
- P2485 [SDOI2011]計算器
- 思路
- Matrix
- 思路
- 代碼
Baby-step Giant-step
問題
在 \(O(\sqrt{p})\) 的時間內求解
\[a^x \equiv b \pmod p \]其中 \(a\perp p\)，方程的解 \(x\) 滿足 \(0 \le x < p\)，
演算法
首先根據費馬小定理 \(a^{p-1}\equiv1\pmod{p}\)，不難發現 \(1\sim p-1\) 是一個回圈節，也就是說只用判斷 \(1\sim p-1\) 這些數里是否存在一個方程的解 \(x\) 即可，
但是這個范圍仍然很大，直接 \(O(p)\) 跑肯定不行，
令 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，則 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\)，
則 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\)，
由于 \(A,B\) 不大，我們可以列舉出所有 \(a^{B} b\) 和 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值，用 map 存下所有 \(a^{B} b\) 的取值，再查找 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值是否出現過即可，
注意在求出滿足 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\) 的合法 \(A,B\) 后還要推回到 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\) 才能得到解 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，這一步要求 \(a\perp p\)，但不要求 \(p\in\mathbb{P}\)，
時間復雜度：\(O(\sqrt{p}\log_2\sqrt{p})\)，
你想更快的話你用哈希表也行，
例題
Discrete Logging
板子題，放一份代碼，
代碼
點擊查看代碼
inline ll FastPow (ll a, ll b, ll P) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P, b >>= 1;
}
return ans;
}
inline void Solve () {
ll qp = ceil (sqrt (p));
_for (i, 0, qp) h[n * FastPow (b, i, p) % p] = i;
ll t = FastPow (b, qp, p), num = 1;
_for (i, 1, qp) {
num = num * t % p;
if (h[num]) {
ans = (i * qp % p - h[num] + p) % p;
return;
}
}
return;
}
P3306 [SDOI2013] 亂數生成器
思路
推式子題，
\[\begin{aligned} x_{i} &\equiv x_{i-1}a+b \pmod{p}\\ &\equiv (x_{i-2}a+b)a+b \pmod{p}\\ &\equiv x_{i-2}a^2+ab+b \pmod{p}\\ &\equiv (x_{i-3}a+b)a^2+ab+b \pmod{p}\\ &\equiv x_{i-3}a^3+a^2b+ab+b \pmod{p}\\ &\equiv x_{1}a^{i-1}+b(\sum_{k=0}^{i-2}a^{k}) \pmod{p}\\ &\equiv x_{1}a^{i-1}+b\frac{1-a^{i-2}}{1-a} \pmod{p}\\ \end{aligned} \]那么：
\[\begin{aligned} x_{1}a^{i-1}+b\frac{a^{i-1}-1}{a-1} &\equiv t \pmod{p}\\ x_{1}a^{i-1}+\frac{a^{i-1}b}{a-1} - \frac{b}{a-1} &\equiv t \pmod{p}\\ a^{i-1}(x_{1}+\frac{b}{a-1}) &\equiv t + \frac{b}{a-1} \pmod{p}\\ a^{i-1} &\equiv \frac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\\ \end{aligned} \]令 \(i - 1 = A \left \lceil \sqrt p \right \rceil - B\)，則 \(a^{A \left \lceil \sqrt p \right \rceil - B} \equiv \dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\)，
則：
\[\begin{aligned} a^{A \left \lceil \sqrt p \right \rceil} &\equiv a^{B}\dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p} \end{aligned} \]就可以跑 BSGS 了，
但是還有幾個細節：
- \(x1=t\)：答案為 \(1\)，
- \(a=0\)：如果 \(b=t\)，答案為 \(2\)，否則為 \(-1\)，
- \(a=1\)：此時 \(x_i=x_1+(i-1)b\)，算逆元即可，
P2485 [SDOI2011]計算器
思路
是不是再來一個 CRT 就同余全家桶了，
裸的逆元和 BSGS，但是題目只保證 \(p\in\mathbb{P}\) 不保證 \(y\perp p\)，需要特判一下 \(p\) 是否為 \(y\) 的倍數，
if (!y) { ans = (z % p ? -1 : 1); return; }
Matrix
思路
定義一個矩陣的類然后直接跑就行，感覺沒啥大區別，
代碼
點擊查看代碼
const ll N = 110;
namespace SOLVE {
ll n, p, ans;
class Matrix {
public:
ll len, m, ma[N][N];
inline void Init (ll l, ll md) {
len = l, m = md;
memset (ma, 0, sizeof (ma));
_for (i, 1, l) ma[i][i] = 1;
return;
}
inline void Print () {
_for (i, 1, n) {
_for (j, 1, n) {
printf ("%lld ", ma[i][j]);
}
puts ("");
}
puts ("");
return;
}
ll* operator [] (ll x) { return ma[x]; }
Matrix operator * (Matrix another) const {
Matrix ans;
ans.Init (len, m);
memset (ans.ma, 0, sizeof (ans.ma));
_for (i, 1, len) _for (j, 1, len) _for (k, 1, len)
ans[i][j] = (ans[i][j] + ma[i][k] * another[k][j] % m) % m;
return ans;
}
bool operator == (Matrix another) const {
_for (i, 1, n) _for (j, 1, n) if (ma[i][j] != another[i][j]) return 0;
return 1;
}
bool operator < (Matrix another) const {
_for (i, 1, len) _for (j, 1, len) {
if (ma[i][j] < another[i][j]) return 1;
if (ma[i][j] > another[i][j]) return 0;
}
return 0;
}
} a, b;
std::map <Matrix, ll> mp;
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline Matrix FastPow (Matrix a, ll b, ll P) {
Matrix ans;
ans.Init (n, P);
while (b) {
if (b & 1) ans = ans * a;
a = a * a, b >>= 1;
}
return ans;
}
inline void In () {
n = rnt (), p = rnt ();
a.Init (n, p), b.Init (n, p);
_for (i, 1, n) _for (j, 1, n) a[i][j] = rnt ();
_for (i, 1, n) _for (j, 1, n) b[i][j] = rnt ();
return;
}
inline void Solve () {
ll qp = ceil (sqrt (p));
_for (i, 0, qp) mp[b] = i, b = b * a;
a = FastPow (a, qp, p);
Matrix mat; mat.Init (n, p);
_for (i, 1, qp) {
mat = mat * a;
if (mp[mat]) {
ans = (i * qp % p - mp[mat] + p) % p;
return;
}
}
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
本文來自博客園，作者：Keven-He，轉載請注明原文鏈接：https://www.cnblogs.com/Keven-He/p/BabyStepGiantStep.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549652.html
標籤：其他
下一篇：斜率優化入門