题解：P10373 [AHOI2024 初中组] 立方根
abc1856896
·
·
题解
题目大意
给定 t 个 x_i，输出：
\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor
## 错误解法
我们可以先预处理出完全立方数，再每次从 $\bm 1$ 开始计算即可。
代码
```cpp
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define MAX_X 10000
using namespace std;
int a [MAX_X+5] ;
void init () {
for ( int i = 1 ; i <= 10000 ; i++) {
a [i] = ( i * i * i );
}
return ;
}
void solve () {
int x ;
cin >> x;
int ans=0,i=1;
for ( ; i <= 10000 ; i++){
if( a[i] > x) {
break ;
}
ans += ( a[i] - a[ i - 1] ) * (i - 1);
}
cout << ans + (i - 1) * (x - a [i - 1] + 1) << "\n" ;
}
signed main () {
init () ;
int T;
cin >> T ;
while( T-- ){
solve() ;
}
return 0 ;
}
```
这份代码的时间复杂度为 ${O(q\sqrt[3]{x})}$，只能拿 $70$ 分。
## 正解
考虑优化。从上面的代码我们可以知道超时的原因是每次从 $\bm 1$ 开始枚举。而结合题目我们可以知道 **$x_i$ 单调递增**。所以我们可以从上一次的 $p$ 开始枚举即可。
代码
```cpp
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
#define MAX_X 10000
using namespace std;
int a [MAX_X+5] ;
void init () {
for ( int i = 1 ; i <= 10000 ; i++) {
a [i] = ( i * i * i );
}
return ;
}
int i = 1 , ans = 0;
void solve () {
int x ;
cin >> x;
for ( ; i <= 10000 ; i++){
if( a[i] > x) {
break ;
}
ans += ( a[i] - a[ i - 1] ) * (i - 1);
}
cout << ans + (i - 1) * (x - a [i - 1] + 1) << "\n" ;
}
signed main () {
init () ;
int T;
cin >> T ;
while( T-- ){
solve() ;
}
return 0 ;
}
```
增加了这个优化的效率非常高，每个测试点都在 $191ms$ 内解决。