题解：P10373 [AHOI2024 初中组] 立方根

原题链接

• 洛谷 P10373 [AHOI2024 初中组] 立方根

解题思路

令：

$$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}$$

由于 cbrt(x) 或 pow(x,1.0/3) 可能会有精度误差，可以手写二分开立方根。

参考代码

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

using ll=long long;
ll cube_root(ll x)
{
	ll l=0,r=100000;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(mid*mid*mid>x)r=mid;
		else l=mid+1;
	}
	return l-1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin>>q;
	while(q--)
	{
		ll x;
		cin>>x;
		ll t=cube_root(x);
		cout<<(x+1)*t-(t*t*t*t+2*t*t*t+t*t)/4<<'\n';
	}
	return 0;
}