$\sum_{i=1}^n\sum_{j=1}^igay(j)$

未分类

---

设$gay(i)=|\mu(i)|i^2$，求$\sum_{i=1}^n\sum_{j=1}^i gay(j)$

$f(n)=\sum_{i=1}^ngay(i)=\sum_{i=1}^{\sqrt n}\mu(i)i^4\sum_{j=1}^{\lfloor \frac{n}{i^2}\rfloor}j^2=\sum_{i=1}^{\sqrt n}\mu(i)i^4h(\lfloor n/i^2 \rfloor)$

$$h(n)=\sum_{i=1}^ni^2$$
$$\begin{align*} ans=&\sum_{i=1}^nf(i)\\ &= \sum_{i=1}^n\sum_{j=1}^{\sqrt i}\mu(j)j^4h(i/j^2)\\ &= \sum_{j=1}^{\sqrt n}\mu(j)j^4\sum_{i=1}^nh(i/j^2) \end{align*}$$
枚举$j$计算即可，再说下求解$\sum_{i=1}^nh(\lfloor i/j^2 \rfloor)$.
显然$\sum_{i=1}^nh(i/j^2)=j^2*\left(h(0)+h(1)+...+h(n/j^2-1)\right)+(n-\lfloor n/j^2\rfloor j^2+1)*h(n/j^2)$

$s(n)=\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{j=1}^ij^2=\sum_{j=1}^nj^2(n-j+1)$
$s(n)=(n+1)\sum_{j=1}^nj^2-\sum_{j=1}^nj^3$
$\sum_{i=1}^ni^2=n(n+1)(2n+1)/6$
$\sum_{i=1}^ni^3=n^2(n+1)^2/4$
乘法会溢出，快速乘会超时，需要优秀的常数