题解：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_{j=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;
}