自动搬运

查看原文

来自洛谷，原作者为

	undefined_Ryan 这个家伙很懒，什么也没有留下

搬运于2025-08-24 23:13:55，当前版本为作者最后更新于2025-05-04 08:31:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下记 $p=998244353$。

首先考虑一个简化版本的问题：

小 A 和小 B 玩若干轮游戏，每轮获胜者加 $2$ 分，失败者加 $1$ 分，已知 $a,b$ 是两人分数模 $k$ 的余数，求游戏最小轮数。

即：有 $2$ 个非负整数 $A,B$，满足 $\frac{\max\{A,B\}}{\min\{A,B\}}\le2$ 且 $3|A+B$，已知它们模 $k$ 的余数 $a,b$，求 $\frac{A+B}3$ 的最小值。

跑一下 BSGS 可以得到 $k$（即 $2$ 模 $p$ 的阶）是 $\frac{p-1}2=499122176$，这个数并不是 $3$ 的倍数，所以通过将 $a,b$ 增加同等数量的 $k$ 可以达到条件，而且所需的数量不大。直接贪心：每次取 $a,b$ 中较小的一个增加 $k$，直到满足条件。这个子问题的时间复杂度是 $O(1)$，可能相对某些数学做法更慢，但是足够通过本题。

那么我们接下来就只需要解决以下这个问题：

$m$ 次询问，每次询问一个正整数 $n$，要求输出 $2^x\equiv n\pmod p$ 的最小非负整数解或判断无解（$m\le2\times10^5$）。

这不就是一个 BSGS 裸题吗？等等：BSGS 是 $O(\sqrt p)$ 的，这样总复杂度就是 $10^9$ 量级的，显然不能通过。

我们仔细研究一下 BSGS 的实现（假设你已经学过了 BSGS），然后考虑优化。

定义一个常数 $k=\lceil\sqrt p\rceil$。然后先预处理 $ba^B$ 的所有取值（$0\le B<k$），用数据结构存储，再枚举 $a^{Ak}$ 的值（$1\le A\le k$ 或 $1\le A\le\lceil\frac pk\rceil$），找到 $a^{Ak}\equiv ba^B\pmod p$，则有 $a^{Ak-B}\equiv b\pmod p$。（参考 OI Wiki 上的实现）

$ba^B$ 是对每组询问不同的，而 $a$ 是固定的，所以 $a^{Ak}$ 是相同的。考虑颠倒如上操作顺序。因为答案的上限是 $\frac{p-1}2=499122176$，我们可以进行进一步优化。

定义一个常数 $k$。然后先预处理 $a^{Ak}$ 的所有取值（$1\le A\le\lceil\frac p{2k}\rceil$），用数据结构存储，再枚举 $ba^B$ 的值（$0\le B<k$），找到 $a^{Ak}\equiv ba^B\pmod p$，则有 $a^{Ak-B}\equiv b\pmod p$。

总时间复杂度为 $O(\frac p{2k}+mk)$。取 $k=\lceil\sqrt\frac p{2m}\rceil=50$，则时间复杂度为 $O(\sqrt{pm})$，量级为 $10^7$，可以通过本题。

注：这里假设哈希表的单次操作复杂度为 $O(1)$，因为一些显然的原因，需要手写哈希表。$a^{Ak}$ 分布较为均匀且与输入数据无关（不会被卡），所以直接取模即可，单个链表内不会超过 $10$ 个数据。注意 BSGS 算法无法解决答案为 $0$ 的情况，需要特判。

提交记录