自动搬运

查看原文

来自洛谷，原作者为

	wkywkywky 左右两个通电螺线管

搬运于2025-08-24 23:08:44，当前版本为作者最后更新于2025-01-22 00:21:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

让我们忽略掉一些细节，原问题可以规约下面的问题。

$\sum b=O(V),\forall b>0$ 求 $\gcd{b}$。

最多 $\sqrt{V}$ 个 $b>\sqrt{V}$。

如果没有 $b\leq \sqrt{V}$，有 $n\leq \sqrt{V}$。

直接做 $\gcd$ 时间复杂度为 $O(\sqrt{V}\ln V)$。

否则 $\exist b\leq \sqrt{V}$，其他数对其取模。

使用 $O(W)-O(1)$ 的值域 $\gcd$ 即可。

时间复杂度为 $O(n+\sqrt{V})$。