「LuoguP3846」「TJOI2007」可爱的质数 / BSGS 学习笔记

AutumnKite

笔记

发布于：2019年2月15日

大步小步法（Baby Step Giant Step, BSGS），用于解决求形如 \(a^x\equiv b \pmod P\) 的最小非负整数解，其中\((a,P)=1\)。

求解

显然 \(x\) 可以表示为 \(i\cdot t-j\) 的形式，其中 \(t\) 是常数。那么原方程化为 \[\begin{aligned} a^{it-j} &\equiv b &\pmod P \\ \frac{a^{it}}{a^j} &\equiv b &\pmod P \\ a^{it}&\equiv ba^j &\pmod P \end{aligned}\]

又根据欧拉定理可得，\(a^b\equiv a^{b\bmod \varphi(P)}\pmod P\)，所以最小非负整数解一定满足 \(0\le x < \varphi(P)\)。

那么 \(t\) 取 \(\lfloor \sqrt{\varphi(P)}\rfloor\) 时，\(i,j\) 的数量都是 \(\mathcal O(\sqrt{P})\) 的。所以我们只要对于所有的 \(i\) 求出 \(a^{it}\)，对于所有的 \(j\) 求出 \(ba^j\)，然后匹配即可。

具体实现时，可以用 map 或 hashmap 实现快速查找。

代码

「TJOI2007」可爱的质数

#include <cstdio>
#include <cmath>
#include <map>
int P, a, b;
int BSGS(int a, int b){
    a %= P, b %= P;
    if (a == 0) return b == 0 ? 1 : -1;
    std :: map<int, int> M;
    int t = sqrt(P) + 1, x = 1, y;
    for (register int i = 0; i < t; ++i, x = 1ll * x * a % P)
        M[1ll * x * b % P] = i;
    y = x;
    if (M.count(1) && M[1] == 0) return 0;
    for (register int i = 1; i <= t; ++i, x = 1ll * x * y % P)
        if (M.count(x)) return i * t - M[x];
    return -1;
}
void write_ans(int x){
    if (x < 0) printf("no solution\n");
    else printf("%d\n", x);
}
int main(){
    scanf("%d%d%d", &P, &a, &b);
    write_ans(BSGS(a, b));
}

更新于：2020年3月26日

TJOI

BSGS

「AT1727」「CODE FESTIVAL 2015 OKINAWA OPEN」Enormous XOR Rectangle

题目传送门题意 \(H\times W\) 的矩阵，第 \(i(0\le i< H)\) 行第 \(j(0\le j< W)\) 列的数为 \(iW+j\)。选一个子矩阵，...

「AT1726」「CODE FESTIVAL 2015 OKINAWA OPEN」Dictionary for Shiritori Game

题目传送门题意给定大小为 \(n\) 的字符集和 \(m\) 个单词，第 \(i\) 个单词以字符 \(a_i\) 开头，以字符 \(b_i\) 结尾。 Snuke 和 Sothe 轮...