Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên ta sẽ chia đoạn [1,n] thành những đoạn con để ta dể quản lý trong việc tính tổng, cụ thể như sau:

• Với \(i\in [1^3,2^3-1]\implies \left \lfloor{\sqrt[3]{i}}\right\rfloor=1\)

• Với \(i\in [2^3,3^3-1]\implies \left \lfloor{\sqrt[3]{i}}\right\rfloor=2\)

• Với \(i\in [3^3,4^3-1]\implies \left \lfloor{\sqrt[3]{i}}\right\rfloor=3\)

...

• Với \(i\in [k^3,n]\implies \left \lfloor{\sqrt[3]{i}}\right\rfloor=k\)

Trong đó: \(k\) phải thoả mãn: \(k^3\le n<(k+1)^3\)

Khi đó, công việc lúc này của ta chỉ là đi tìm \(k\) thoả mãn: \(k^3\le n<(k+1)^3\) và sau đó duyệt một vòng for từ 1 đến k để tính tổng là xem như bài toán đã được giải quyết xong:

Công thức tổng quát của bài toán như sau: \(S = \sum\limits_{i=1}^{k-1}((i+1)^3-1-i^3+1)*i + k*(n-k^3+1)\)

Để xác định được k ta có thể sử dụng chặt nhị phân, cụ thể như sau:

long long sqrt3(long long n)
{
    long long l = 1, r = 1000000;
    while (l <= r)
    {
        long long mid = (l + r) / 2;
        if ((long long)mid * mid * mid <= n)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return l - 1;
}

Như vậy, bài toán đã được giải quyết xong, tuy nhiên, vì tổng này khá lớn, nên ta phải sử dụng BigNum để giải quyết !

Độ phức tạp: \(O(\sqrt[3]{n})\)

Ps: Nếu đã cố gắng hết sức nhưng vẫn chưa ac, các bạn có thể tham khảo code tại đây