Tính tổng 1 + 2 + ... + n (VL02)

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Mã bài VL02

Đề bài

Cho số nguyên dương $n$. Hãy tính

$$S = 1 + 2 + 3 + \ldots + n$$

Dữ liệu vào:

Một dòng chứa số nguyên dương $n$.

Kết quả:

In ra giá trị $S$.

Giới hạn:

• $1 \le n \le 10^9$

Lưu ý: $S$ có thể lên tới khoảng $5 \cdot 10^{17}$, vượt phạm vi kiểu int.

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5

Ví dụ 1 – output

15

Giải thích:

• $S = 1 + 2 + 3 + 4 + 5 = 15$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Ý tưởng

Cách "vòng lặp" là cộng dồn S += i với i từ 1 tới n. Nhưng n tới 10^9 thì phải lặp 1 tỉ lần – Python chắc chắn quá thời gian. Thầy dùng công thức Gauss:

$$S = \frac{n(n+1)}{2}$$

Ví dụ n = 5: 5 · 6 / 2 = 15. Ghép cặp 1 + 5 = 2 + 4 = 6... nên tổng là n cặp "nửa" có giá trị n + 1.

Lưu ý / bẫy thường gặp

• Tràn số: với n = 10^9, n·(n+1) khoảng 10^{18} – phải dùng long long cho cả n, không chỉ cho S (nếu n là int thì n*(n+1) vẫn tính bằng int và tràn trước khi gán).
• Lặp từng số bằng Python thì quá chậm với n lớn.
• Nhớ đúng công thức n(n+1)/2, không phải n(n-1)/2.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇