P10373 [AHOI2024 初中组 / 科大国创杯初中组 2024] 立方根

解题思路

令：

$$t=\left\lfloor \sqrt[3]x \right\rfloor$$

则：

$$\begin{aligned} \sum_{j=1}^x \left\lfloor j^{\frac{1}{3}} \right\rfloor &= \sum_{i=1}^x \left\lfloor \sqrt[3]j \right\rfloor \\ &= \sum_{j=1}^{t^3-1} \left\lfloor \sqrt[3]j \right\rfloor + \sum_{j=t^3}^{x} \left\lfloor \sqrt[3]j \right\rfloor \\ &= \sum_{i=1}^{t-1} \sum_{j=i^3}^{(i+1)^3-1} \left\lfloor \sqrt[3]j \right\rfloor + \sum_{j=t^3}^{x} \left\lfloor \sqrt[3]j \right\rfloor \\ &= \sum_{i=1}^{t-1} \sum_{j=i^3}^{(i+1)^3-1} i + \sum_{j=t^3}^{x} t \\ &= \left ( \sum_{i=1}^{t-1} \left((i+1)^3-i^3\right) \cdot i \right ) + (x-t^3+1) \cdot t \\ &= \left ( \sum_{i=1}^{t-1} 3i^3+3i^2+i \right ) + (x-t^3+1) \cdot t \\ &= \frac{3}{4} t^4- \frac{1}{2} t^3 -\frac{1}{4} t^2-t^4+(x+1) \cdot t \\ &= (x+1) \cdot t - \frac{t^4+2t^3+t^2}{4} \end{aligned}$$

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin>>q;
	while(q--)
	{
		ll x;
		cin>>x;
		ll t=cbrt(x+0.5);
		cout<<(x+1)*t-(t*t*t*t+2*t*t*t+t*t)/4<<'\n';
	}
	return 0;
}