题解：P15395 幻影之春 / phantom

原题Link

有点牛的数学题。

题意

求

$$\sum_{i=1}^n \lfloor\sqrt{i}\rfloor$$

Solution

注意到 $n\le 10^{18}$ 发现是数学题。

这里介绍 $O(1)$ 的做法。

首先将 $\lfloor\sqrt{x}\rfloor$ 拆解。 发现 $\lfloor\sqrt{x}\rfloor$ 是存在一个 $j$ 使 $j^2=x$，要使这个 $j^2$ 无限接近于 $\lfloor\sqrt{x}\rfloor$，所以可以得出以下式子:

$$\lfloor\sqrt{x}\rfloor=\sum_{j=1}^{\infty}[j^2\le x]$$

把这个式子代替 $\lfloor\sqrt{i}\rfloor$，放进原式。

$$\begin{aligned} \sum_{i=1}^n \lfloor\sqrt{i}\rfloor&=\sum_{i=1}^{n}\sum_{j=1}^{\infty}[j^2\le x]\\ &=\sum_{j=1}^{\lfloor\sqrt{n}\rfloor}\sum_{i=j^2}^n 1\\ &=\sum_{j=1}^{\lfloor\sqrt{n}\rfloor} (n-j^2+1)\\ &=(n+1)\times\lfloor\sqrt{n}\rfloor-\sum_{j=1}^{\lfloor\sqrt{n}\rfloor} j^2 \end{aligned}$$

平方和公式如下：

$$\sum_{i=1}^n i^2=\frac{n\times (n+1) \times (2n+1)}{6}$$

将该公式的 $n$ 代入 $\lfloor\sqrt{x}\rfloor$，得：

$$\text{ans}=(n+1)\times \lfloor\sqrt{x}\rfloor-\frac{\lfloor\sqrt{x}\rfloor\times(\lfloor\sqrt{x}\rfloor+1)\times(2\times\lfloor\sqrt{x}\rfloor+1)}{6}$$

时间复杂度 $O(1)$。