Bedan Contest #03 - A - Bài tập
Xem PDFMột năm mới sắp đến nên quyết định chuẩn bị bài cho Bedan Contest #03 như là một món quà nho nhỏ tới những thành viên của TLEoj. Chỉ còn vài ngày nữa là đã đến ngày diễn ra nhưng vẫn chưa có ý tưởng nào. Một hôm, khi đọc sách về toán học thì cậu đã thấy được một vài công thức tính tổng các dãy số liên tiếp phổ biển như sau.
- \sum_{i = 1}^n i = \frac{n\times (n+1)}{2}.
- \sum_{i = 1}^n i^2 = \frac{n\times (n+1)\times (2\times n+1)}{6}.
- \sum_{i = 1}^n i^3 = (\frac{n\times (n+1)}{2})^2.
- ...
nhận ra các công thức trên đều tính tổng dãy số có số mũ là số nguyên. Bỗng cậu thắc mắc rằng có cách nào để tính nhanh \sum_{i = 1}^n \lfloor \sqrt{i} \rfloor hay không. Vì đang bí ý tưởng ra bài cho Bedan Contest #03 nên quyết định đưa bài này vào để mời các bạn giải thử. Bạn hãy thử sức với bài này nhé.
Nếu như bạn vẫn không biết \lfloor n \rfloor là gì thì nó là n được làm tròn xuống, như \lfloor 6.9 \rfloor = 6.
Input, Output and Scoring
Input
- Số nguyên dương t (1 \le t \le 10^5).
- t dòng tiếp theo, mỗi dòng gồm 1 số nguyên dương n (1 \le n \le 10^{18}).
Output
- Với mỗi dòng, hãy in ra kết quả thỏa mãn.
Scoring
- Subtask 1 (20\%): 1 \le n \le 10^6.
- Subtask 2 (30\%): 1 \le n \le 10^{12}.
- Subtask 3 (50\%): Không giới hạn gì thêm.
Test
Input
3
4
6
9
Output
5
9
16
Note
- \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor = 1 + 1 + 1 + 2 = 5.
- \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor = 1 + 1 + 1 + 2 + 2 + 2 = 9.
- \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor + \lfloor \sqrt{7} \rfloor + \lfloor \sqrt{8} \rfloor + \lfloor \sqrt{9} \rfloor = 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 3 = 16.
Bình luận