Hướng dẫn cho Tổng phần nguyên (TS10LQĐ 2015)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

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:

C++
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


Bình luận