P4466

· · 题解

一个不太一样的思路？

先忽略 a\lt b 的条件。

注意到 (a+b)\mid ab 等价于 ab\equiv 0\pmod {(a+b)}，而又有 b\equiv -a\pmod {(a+b)}，所以 -a^2\equiv 0\pmod {(a+b)}，即相当于 (a+b)\mid a^2。

枚举 a，即相当于要求 a^2 的所有因子中，在 [a+1,n+a] 范围的个数的和。

注意到一个数 x=\prod p_i^{\alpha_i}，某个平方数 a^2=\prod \left(p_i^{\beta_i}\right)^2 被它整除当且仅当 \forall i,\alpha_i\le 2\beta_i\implies \beta_i\ge \left\lceil\dfrac {\alpha_i}2\right\rceil。

考虑一个数 x=i^2j，其中 j 为不含平方因子的数，那么我们有 i^2j\mid a^2\implies ij\mid a。

枚举 i\le \sqrt n，那么在 i,\left\lfloor\dfrac n{ij}\right\rfloor 都相同时，j 取值个数必然相同（由于其个数形如一个区间内 ij 倍数的个数）。

枚举 i 后，对 \left\lfloor\dfrac ni\right\rfloor 进行整除分块来枚举 j，那么我们要做的就是枚举区间无平方因子的数的个数，这是一个经典的容斥问题，我们可以通过对平方因子进行容斥得到：

S(n)=\sum_{i=1}^n \mu^2(i) = \sum_{i=1}^{\left\lfloor\sqrt n\right\rfloor}\mu(i)\left\lfloor\frac n{i^2}\right\rfloor

再注意到我们需要计算的所有 S 都是某个 \left\lfloor\dfrac {n}{A}\right\rfloor，所以只有 \mathcal O(\sqrt n) 个，可以记忆化。

最后的时间复杂度为：

\mathcal O\left(\sum_{i=1}^{\left\lfloor\sqrt n\right\rfloor}\left\lfloor\sqrt i\right\rfloor\right)=\mathcal O(n^{0.75})