YY 的 GCD 推导（莫比乌斯反演）

· · 算法·理论

题意明确。

\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) 复杂度做完了