Tổng lẻ từ 1 đến N

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Kiểu dữ liệu

Đề bài

Cho số nguyên dương $N$. Hãy tính tổng các số lẻ từ $1$ đến $N$ (gồm cả $N$ nếu $N$ lẻ).

Dữ liệu vào:

Một số nguyên dương $N$.

Kết quả:

Tổng các số lẻ từ $1$ đến $N$.

Giới hạn:

• $1 \le N \le 10^6$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 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

9

Ví dụ 2 – input

3

Ví dụ 2 – output

4

• Ví dụ 1: $1 + 3 + 5 = 9$.
• Ví dụ 2: $1 + 3 = 4$.

Nguồn: phỏng theo bài "TỔNG LẺ" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Cộng $1 + 3 + 5 + \ldots$ không vượt quá $N$. Thay vì duyệt mọi số rồi kiểm tra lẻ, ta cho biến lặp nhảy 2 bước: $1, 3, 5, \ldots$ Hai điểm cần chú ý: phải cộng cả $N$ khi $N$ lẻ, và tổng tới $2{,}5 \cdot 10^{11}$ – vượt int.

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

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngnhảy 2 bướcLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $1 \le N \le 10^6$.

Test	Nội dung kiểm tra
1–10	Ví dụ đề, $N = 1, 2$, $N$ nhỏ chẵn và lẻ
11–14	$N$ quanh $92\,681$: chỗ tổng bắt đầu vượt giới hạn int
15–20	$N$ lớn tới $10^6$, chẵn và lẻ

Ý tưởngCho i nhảy 2 bước

Biến tong = 0; vòng lặp for(i = 1; i <= n; i += 2) cho i lần lượt là $1, 3, 5, \ldots$ – toàn số lẻ, không cần kiểm tra – và cộng vào tong.

Điều kiện i <= n (có dấu bằng) đảm bảo khi $N$ lẻ thì $N$ cũng được cộng: ví dụ 1, $N = 5$: $1 + 3 + 5 = 9$.

Chọn kiểu dữ liệu

Với $N = 10^6$ có $500\,000$ số lẻ, tổng $= 500\,000^2 = 2{,}5 \cdot 10^{11}$ (tổng $k$ số lẻ đầu tiên bằng $k^2$) → tong phải là long long. Tổng vượt int ngay từ $N = 92\,681$.

Em nhập $N$ rồi bấm Tiếp để xem i nhảy qua các số lẻ:

N =

Ví dụ nhanh:

Lời giảiVòng lặp for nhảy 2 bước

Chỉ một vòng lặp for với bước nhảy 2.

C++▶ Chạy tay từng dòng codei chạy 1, 3, 5, ... không vượt quá n, cộng dồn vào tong.

Dữ liệu vào (stdin) – sửa thoải mái5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Sau 15 lần lặp, phần còn lại được "tua nhanh" trong một bước.

1. i += 2 là viết tắt của i = i + 2.
2. Python: range(1, n + 1, 2) – tham số thứ ba là bước nhảy; phải là n + 1 để gồm cả $n$ khi $n$ lẻ.
3. Như bài "Dương lẻ", tổng này bằng $k^2$ với $k = (N + 1) / 2$ – nhưng $N \le 10^6$ nên vòng lặp đã đủ nhanh.

Không gian$O(1)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.007s. Bản Python đúng 20/20 test, chạy lâu nhất 0.145s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Tổng kiểu int	10/20	sai test 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Điều kiện i < n (quên $N$ khi $N$ lẻ)	9/20	sai test 1, 2, 3, 6, 8, 11, 13, 15, 17, 18, 20
Bắt đầu i = 0 (thành cộng các số chẵn)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Công thức $k^2$ với $k = N / 2$	9/20	sai test 1, 2, 3, 6, 8, 11, 13, 15, 17, 18, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.007s	Full điểm
	Python	20/20	0.145s	Full điểm
Tổng int	C++	10/20	–	Mất 10 test
i < n	C++	9/20	–	Mất 11 test
Bắt đầu từ 0	C++	0/20	–	Mất 20 test
k = N / 2	C++	9/20	–	Mất 11 test

Ghi chú của mình: với vòng lặp, hãy luôn kiểm tra ba thứ: giá trị bắt đầu, điều kiện dừng (có dấu bằng không?) và bước nhảy.

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 😇