「学习笔记」BSGS
点击查看目录
目录
- 「学习笔记」BSGS
- Baby-step Giant-step
- 问题
- 算法
- 例题
- Discrete Logging
- 代码
- P3306 [SDOI2013] 随机数生成器
- 思路
- P2485 [SDOI2011]计算器
- 思路
- Matrix
- 思路
- 代码
Baby-step Giant-step
问题
在 (O(sqrt{p})) 的时间内求解
]
其中 (aperp p),方程的解 (x) 满足 (0 le x 。
算法
首先根据费马小定理 (a^{p-1}equiv1pmod{p}),不难发现 (1sim p-1) 是一个循环节,也就是说只用判断 (1sim p-1) 这些数里是否存在一个方程的解 (x) 即可。
但是这个范围仍然很大,直接 (O(p)) 跑肯定不行。
令 (x=Aleftlceilsqrt{p}rightrceil-B (0le A, Bleleftlceilsqrt{p}rightrceil)),则 (a^{Aleftlceilsqrt{p}rightrceil-B} equiv b pmod p)。
则 (a^{Aleftlceilsqrt{p}rightrceil} equiv a^{B} b pmod p)。
由于 (A,B) 不大,我们可以枚举出所有 (a^{B} b) 和 (a^{Aleftlceilsqrt{p}rightrceil}) 的取值。用 map
存下所有 (a^{B} b) 的取值,再查找 (a^{Aleftlceilsqrt{p}rightrceil}) 的取值是否出现过即可。
注意在求出满足 (a^{Aleftlceilsqrt{p}rightrceil} equiv a^{B} b pmod p) 的合法 (A,B) 后还要推回到 (a^{Aleftlceilsqrt{p}rightrceil-B} equiv b pmod p) 才能得到解 (x=Aleftlceilsqrt{p}rightrceil-B (0le A, Bleleftlceilsqrt{p}rightrceil)),这一步要求 (aperp p),但不要求 (pinmathbb{P})。
时间复杂度:(O(sqrt{p}log_2sqrt{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] 随机数生成器
思路
推式子题。
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}+bfrac{1-a^{i-2}}{1-a} pmod{p}\
end{aligned}
]
那么:
x_{1}a^{i-1}+bfrac{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})。
则:
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,但是题目只保证 (pinmathbb{P}) 不保证 (yperp 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 another[i][j]) return 0;
}
return 0;
}
} a, b;
std::map 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 >= 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 ("%lldn", ans);
return;
}
}
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net