本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 15:25:13

题意明确。

$$ \begin{aligned} \mathrm{圆柿} &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m [(i, j) = p] \ &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m\sum\limits_{d\mid (i,j)} \mu(d) \ &=\sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m [d\mid i][d \mid j] \ &= \sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n, m)}\mu(d)\lfloor\dfrac n {pd}\rfloor\lfloor\dfrac m {pd}\rfloor \end{aligned} $$

最开始只得到了这个 $O(Tn)$ 的做法，爆零。但是可以再优化一下。设 $u = pd$，则

$$ \begin{aligned} 圆柿 = \sum\limits_{u=1}^{\min(n, m)}\lfloor{\dfrac n u}\rfloor\lfloor\dfrac m u\rfloor\sum\limits_{d\mid u}\mu(\dfrac u d) \end{aligned} $$

然后惊奇地发现后面的柿子可以 $O(V)$ 预处理！

于是本题就用优雅的 $O(V + T\sqrt n)$ 复杂度做完了