题解：P10373 [AHOI2024 初中组] 立方根
woscxk
2024-04-22 11:08:27
# 本蒟蒻的第一篇 tj，如果有问题请各位 dalao 们指出
**Upd On 2024/4/22 16:14 : 因为被 hack 了，我更新了 1 种 $O(t)$ 的数学方法。**
**Upd On 2024/4/28 19:42: 打回后更改了 latex。**
## #1: 暴力！
一看到这题目，首先想到的肯定是暴力，直接去套公式。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
long long output[t];
for(int i=0;i<t;i++){
long long x,sum=0;
cin>>x;
for(int j=1;j<=x;j++){
sum+=floor(cbrt(j));
}
output[i]=sum;
}
for(int i=0;i<t;i++){
cout<<output[i]<<'\n';
}
}
```
然后你就~~成功的~~ TLE 了 (20pts)
$O(xt)$ 的复杂度，$2 \times 10^5 \times 10^{12}=2 \times 10^{17}$ , 严重 TLE。
暴力过不了，我们就得引入另一种方法了。
他就是人见人爱，花见花开，车见车爆胎的
## #2：~~打表！~~
我们可以在程序内部打表，打出每个 $j^{1/3}$ 向下取整的个数
例如样例中提到的 $[\text{1,1,1,1,1,1,1,2,2,2}]$
我们可以理解为 $7$ 个 $1$，$3$ 个 $2$，对应的就是 $[0,7,3]$
在索引为 $x$ 时值为 $y$，就代表有 $y$ 个 $x$
由此，代码也就呼之欲出了
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[10001];//表
int main(){
for(int i=0;i<10001;i++){//打表程序
a[i]=pow(i+1,3)-pow(i,3);
}
int t;
cin>>t;//q
long long output[t]={};//集体输出数组
for(int i=0;i<t;i++){
long long x,sum=0;
scanf("%lld",&x);
for(int j=1;x>0;j++){
if(x>=a[j]){
x-=a[j];
sum+=a[j]*j;
}else{//如果只占一部分，将x消耗完并令x=0
sum+=x*j;
x=0;
}
}
output[i]=sum;
}
for(int i=0;i<t;i++){
printf("%lld\n",output[i]);
}
}
```
复杂度 O ($tx^{1/3}$) ，$2 \times 10^5 \times 10^4=2 \times 10^9$, 无伤通过 subtask #0.
## #3: 数学
感谢 @Breath\_of\_the\_Wild 的 [tj](https://www.luogu.com/article/2ofym2gn) 的指导！
注：$[x]$ 表示 $x$ 向下取整
如 #2 所言，$a_{n}=(i+1)^3-i^3$
而当
$$
x_{i} \ge \sum_{i=1}^{n-1}{x_i}
$$
时，sum 就加上了这一“整块” 的得分。即 $i((i+1)^3-i^3)$ 化简得：$3i^3+3i^2+i$
那么对于整块 1 + 整块 2+…+ 整块 $[n^{1/3}]-1$ 答案为：
$$
\sum_{i=1}^{[n^{1/3}]-1}{(3i^3+3i^2+i)}
$$
设 $[n^{1/3}]=t$。
则化简得：$\frac{3}{4}t^2(t-1)^2+\frac{1}{2}t(t-1)(2t-1)+\frac{1}{2}t(t-1)$。
除了整块的部分，还有零碎的部分：
从 $j=t^3$ 开始，$[j^{1/3}]=t$ 了，到 $n$ 就是 $n-t^3+1$，乘上权重就是 $t(n-t^3+1)$
合起来太麻烦了~~自己算去吧！~~，我们可以将他们分存到两个变量中，但是直接相加是没有任何问题的。
## #4: 上代码！
20 分：
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
long long output[t];
for(int i=0;i<t;i++){
long long x,sum=0;
cin>>x;
for(int j=1;j<=x;j++){
sum+=floor(cbrt(j));
}
output[i]=sum;
}
for(int i=0;i<t;i++){
cout<<output[i]<<'\n';
}
}
```
100 分 unac：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[10001];//表
int main(){
for(int i=0;i<10001;i++){//打表程序
a[i]=pow(i+1,3)-pow(i,3);
}
int t;
cin>>t;//q
long long output[t]={};//集体输出数组
for(int i=0;i<t;i++){
long long x,sum=0;
scanf("%lld",&x);
for(int j=1;x>0;j++){
if(x>=a[j]){
x-=a[j];
sum+=a[j]*j;
}else{//如果只占一部分，将x消耗完并令x=0
sum+=x*j;
x=0;
}
}
output[i]=sum;
}
for(int i=0;i<t;i++){
printf("%lld\n",output[i]);
}
}
```
ac：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n;
int main(){
cin>>T;
while(T--){
cin>>n;
ll l=pow(n,1.0/3);
if(l*l*l<n&&(l+1)*(l+1)*(l+1)<=n) l++;
else if(l*l*l>n) l--;//调整精度
cout<<(l-1)*(l-1)*l*l*3/4+(l-1)*l*(2*l-1)/2+l*(l-1)/2+(n-l*l*l+1)*l<<'\n';
}
return 0;
}
```
温馨小提示：
### ~~不开 long long 见祖宗~~
###### （小声 bb）：~~再次~~望管理大大过审！