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

参考代码

#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;
}