警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」BSGS - 数论

简介

BSGS 可以在 \(O(\sqrt n)\) 的时间内,解出形如 \(a^x\equiv b\pmod P\)\(x\)

普通 BSGS 只能处理 \(\gcd(a,P)=1\) 的情况,使用 exBSGS 可以处理任意 \(a, n, P\) 的数据。

不会 exBSGS,于是咕咕了(

流程

分块思想。考虑令 \(m = \left\lceil\sqrt P\right\rceil\),那么可以将 \(x\) 写成 \(pm - q\) 的形式,其中 \(p \in [0, m], q \in [0, m)\)

所以有

\[ \begin{aligned} a^x & \equiv b \pmod p \\ a^{pm-q} & \equiv b \pmod p \\ a^{pm}a^{-q} & \equiv b \pmod p \\ a^{pm} & \equiv b\cdot a^q \pmod p \\ \end{aligned} \]

于是可以预处理 \(b\cdot a^q\) 扔进 hash 表里,枚举 \(p\) 即可在 \(O(\sqrt P)\) 的时间求出 \(x\)

真暴力……

如果 hash 表要用 STL 或者 pb_ds,建议配上下面的 hash 函数,因为 unordered 系列和 hash_table 都是能卡的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef unsigned long long u;
struct $ {
static u nxt(u x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
int operator()(u x) const {
static const u rnd = std::chrono::steady_clock::now().time_since_epoch().count();
return nxt(x + rnd);
}
};

std::unordered_map<u, qwq, $> mp;

但是一般我不加 23333

例题

P4884 多少个1?

题意

传送门:洛谷 P4884 - 多少个1?

求最小的正整数 \(n\),满足 \(\underbrace{11\cdots1}_n\equiv k\pmod p\)

解法

\(\displaystyle\underbrace{11\cdots1}_n \equiv \frac{10^n-1}9 \equiv k\pmod p\)

\(p\ne3\) 时,上式等价于 \(10^n\equiv9k+1\pmod p\)

于是可以特判 \(p=2,5\) 然后做 BSGS,或者你愿意写 exBSGS 也行吧……

最后特判 \(p=3\) 的情况。

最后这屑题爆 ll,可以用快速乘、龟速乘或者 __int128 处理。

代码

因为懒,所以这份代码没有特判。可以用 \(p=2,3,5\) hack 这份代码。

P2485 [SDOI2011]计算器

题意

传送门:洛谷 P2485 - 计算器

\(T\) 组查询,每组查询给 \(y, z, p\),解出 \(x\)

  • \(y^z\equiv x\pmod p\)
  • \(xy\equiv z\pmod p\)
  • \(y^x\equiv z\pmod p\)

保证 \(p\) 为质数。

解法

板子。

代码