BSGS & exBSGS

Description

给定 $a, b, p$ ，你需要找到最小的满足 $a^x \equiv b \pmod p$ 的 $x$ 。

$T$ 组数据， $\sum \sqrt p \le 5 \times 10^6$ 。

算法一(BSGS: 保证 $\gcd(a,p)=1$ )

令 $B=\lceil \sqrt p \rceil$ ， $t=a^B$ 。

我们先将 $a^0,a^1,\cdots,a^B$ 分别压入哈希表中，接着枚举 $i=0,1,\cdots$ ，同时算出 $\frac {b} {t^{i}}$ 在模意义下的值。如果该值在哈希表中出现过，则我们就得到了答案。

时间复杂度 $O(\sqrt B)$ 。逆元可以用扩展欧几里得算法求解（在 $p$ 为质数的时候也可以用费马小定理），哈希表可以使用 unordered_map 来实现。

算法二(exBSGS)

若不保证 $\gcd(a,p)=1$ ，那么就无法算出 $\frac {b} {t^i}$ 在模意义下的值了，因为 $t^i$ 在模意义下可能不存在逆元。所以我们考虑将其转化为 $\gcd(a,p)=1$ 的情况，这样就能直接套用算法一了。

考虑计算出 $d=\gcd(a,p)$ ，那么问题就转化为求出最小的 $x$ 使得 $(\frac a d)a^{x-1} \equiv \frac b p\pmod {\frac {p} d}$ 。注意到 $\frac a d$ 与 $\frac p d$ 是互质的，所以我们可以计算出 $\frac a d$ 的逆元并将其提到右边，这样就转化为了一个本质相同而规模减小的子问题 $a^{x-1} \equiv {\frac b d}\times {\frac a d}^{-1} \pmod {\frac p d}$ ，可以递归解决。

特别的，当 $d = 1$ 时，我们直接调用 BSGS 就行了。此外，注意特判 $b = 1$ 或 $p = 1$ 的情况，此时应直接返回 $0$ 。同时，要注意假设目前已经递归到了第 $k$ 层（刚开始是第 $0$ 层），那么真正的答案应该还要再加上 $k$ 。

注意到每次 $p$ 都至少除以 $2$ ，所以 $p$ 至多会变化 $\log p$ 次，而每次都要通过辗转相除计算一次 gcd，所以总复杂度是 $O(\log^2 p+\sqrt p)$ 的。

由于 unordered_map 的巨大常数，洛谷上会轻微卡常。

Lucas & exLucas

Description

给定 $n, m, p$ ，求 $\choose m} \ \text{mod} \ p$ 。

$\le n,m \le 10^{18},1 \le p \le 10^6$

算法一(Lucas: 保证 $p$ 为质数)

首先，如果 $n, m < p$ ，那么可以直接阶乘逆元求解。那么 $\ge p$ 的话该怎么办呢？

Lucas 定理给出

$\choose m} \equiv {{\lfloor \frac n p \rfloor} \choose {\lfloor \frac m p \rfloor}} \times {{n \ \text{mod} \ p} \choose m \ \text{mod} \ p} \pmod p$

递归求解即可。

时间复杂度 $O(p+\log_p n)$ 。

算法二(exLucas: 不保证 $p$ 为质数)

首先考虑对 $p$ 进行质因数分解，将其拆分为 $p=\prod_{i=1}^k a_i^{b_i}$ 的形式（ $\forall i \in [1,p]$ ， $a_i$ 为质数），那么只要我们对于每个 $i$ 求出了 $\choose m}$ 对 $a_i^{b_i}$ 取模后的值，通过 CRT 合并就能得到答案了。所以关键在于，当模数为某个质数的若干次方 $p^q$ 的时候，如何算出组合数 $\choose m}$ 在模意义下的值。

考虑计算出 $n!, m!, (n ? m)!$ 中分别包含多少个质因子 $p$ 。假设分别有 $x, y, z$ 个，那么 $\choose m}$ 中就包含了 $x ? y ? z$ 个质因子 $p$ 。那么，如果 $\ge q$ ，那么显然 $\choose m} \equiv 0 \pmod {p^q}$ 。否则，我们考虑分别求出 $n!, m!, (n ? m)!$ 去掉所有质因子 $p$ 后的值 $u, v, w$ ，那么答案即为 $\frac {u!} {v!w!}$ 模 $p^{q-(x-y-z)}$ 再乘上 $p^{x-y-z}$ 的值，显然可以通过扩展欧几里得算法求出。

所以关键在于，如何求出把 $n!$ 中的所有质因子 $p$ 去掉后的值 $f (n, p)$ 。不难发现， $f (n, p)$ 的组成分为三个部分，其中第一个部分是 $[1, n]$ 中 $p$ 的倍数，第二个部分是 $\times \lfloor \frac {n} {p} \rfloor]$ 中非 $p$ 的倍数，第三个部分就是 $\times \lfloor \frac {n} {p} \rfloor,n]$ 中的所有数。对于第一个部分，我们可以递归求解；对于第二个部分，不难发现其乘积由若干个连续段组成，而根据威尔逊定理，其中任何一个连续段的乘积均为 $? 1$ ，所以这一部分的贡献就是 $(-1)^{\lfloor \frac n p \rfloor}$ ；而对于第三个部分，注意到其乘积在模意义下与 $\ \text{mod} \ p)!$ 相等，通过预处理出各个数在模意义下的的阶乘，每次就可以 $O (1)$ 调用了。