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

思路：

先通过此程序列出部分立方根向下取整的情况。

#include<bits/stdc++.h>
using namespace std;
long long s[20000000];
long long jia(long long x,long long y){
	long long sum=0;
	for(int i=x+1;i<=y;i++)sum+=cbrt(i);
	return sum;
}
int main(){
	long long x,y=0;
	long long last=0,las=0;
	for(int i=1;i<=1e6;i++){
		s[i]=s[i-1]+cbrt(i);
		if(s[i]-s[i-1]!=last)cout<<i<<" "<<s[i]<<"\n",last=s[i]-s[i-1];
	}
		
	
	return 0;
}

可以发现每次当 $i$ 为某数的立方时，立方根向下取整的结果会增加一。

所以我们可以定义一个变量 $l$ 表示现在历遍的立方根，这样我们就不用从一历遍到十的十二次方了，只用历遍到十的十二次方的立方根了。

然后是如何计算，第一，当 $l+1$ 的立方也就是下一个立方的值大于我们输入的 $x+1$ 时，我们取较小的数，第二，当 $l$ 的立方也就是现在的立方的值大于上一个输入的 $x$ 的值时，我们在两个数取较大值，然后将 $l+1$ 的立方和 $x+1$ 的较小值与 $l$ 的立方和上一个 $x$ 的较大值相减，这样子做是为了防止多算和少算，然后总和加上就行了，循环条件是 $l$ 的立方小于等于现在的 $x$。

代码：

代码中的注释和思路里写的是一样的。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long// 无根号 long long 
ull T,x,l;
ull f(ull n){// 计算立方 
	return n*n*n;
}
int main(){
	cin>>T;
	ull l=1,sum=0,last=0;
	for(ull i=1;i<=T;i++){
		cin>>x;
		while(f(l)<=x){//也可以改成 for 循环
			sum+=l*((min(f(l+1),x+1))-max(f(l),last+1));
			//f(l+1) 是下一个立方的值与 x+1 取最小值约等于特判了如果下一个立方大于 x 的情况 
			//max(f(l),last+1) 是取现在的立方的值与上一个的 x+1（last+1） 中的最大值
			//min((l+1)*(l+1)*(l+1),x+1))-max(l*l*l,last+1) 是为了防止少算和多算 
			l++;// 每次 l++ 
		}
		l--;// 因为最后一次 ++ 的 l 是不满足的没有计算所以要 --
		cout<<sum<<"\n";// 输出
		last=x;// 赋值 
	}
	return 0;// return 好习惯听说比赛里没有爆 0
}