自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:16:10，当前版本为作者最后更新于2024-12-07 15:39:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

经典结论：$(x_1,y_1)$ 能看到 $(x_2,y_2)$ 当且仅当 $\gcd(x_1-x_2,y_1-y_2)=1$。

枚举 $x$ 坐标，那么对于点 $i$，要对所有满足 $\gcd(x-x_i,y-y_i)=1$ 的 $y$ 计算贡献。记前者为 $\Delta x$，问题转化为：

• 长度为 $Y$ 的序列，维护下标与 $\Delta x$ 互质的位置加 $1$，最后求整个序列。

容斥，先全部加 $1$，枚举 $\Delta x$ 的每个因子 $d$，将所有满足 $i|d$ 的位置加上 $\mu(d)$ 即可。满足 $\mu(d)\not=0$ 的 $d$ 只有 $2^{\omega(V)}$ 个，最大也只有 $16$，可以接受。

由于这里还有一个 $y\bmod d$ 的位移，直接上根号分治即可。

设阈值为 $B$，则复杂度为 $\mathcal O(XY+Xn2^{\omega(V)}\cdot\dfrac{Y}{B}+XYB)$，取 $B=\mathcal O(\sqrt{n2^{\omega(V)}})$ 最优，复杂度为 $\mathcal O(XY\sqrt{n2^{\omega(V)}})$。

因为 $>B$ 的因子很少，这个根号分治是跑不满的，$X=Y=n=V=2\times10^3$ 的数据直接 $0.5\text{s}$ 过。