Tổng chẵn từ a đến b

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

Đề bài

Cho hai số nguyên dương $a$ và $b$. Hãy tính tổng các số chẵn trong đoạn $[a, b]$ (gồm cả $a$ và $b$).

Dữ liệu vào:

Một dòng gồm hai số nguyên dương $a$ và $b$ cách nhau bởi dấu cách.

Kết quả:

Tổng các số chẵn trong đoạn $[a, b]$. Nếu đoạn không có số chẵn nào thì in ra $0$.

Giới hạn:

• $1 \le a \le b \le 2^{26}$ ($2^{26} = 67\,108\,864$)

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

1 5

Ví dụ 1 – output

6

Ví dụ 2 – input

2 4

Ví dụ 2 – output

6

• Ví dụ 1: các số chẵn trong đoạn $[1, 5]$ là $2, 4$; tổng bằng $6$.
• Ví dụ 2: các số chẵn trong đoạn $[2, 4]$ là $2, 4$ (tính cả hai đầu mút); tổng bằng $6$.

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

Lời mở đầu

Duyệt từ $a$ tới $b$, gặp số chẵn thì cộng vào tổng. Đoạn dài tới $2^{26} \approx 6{,}7 \cdot 10^7$ số và tổng lên tới khoảng $1{,}1 \cdot 10^{15}$ – nên cần long long. Bài này còn là dịp để thấy Python chậm hơn C++ nhiều: cùng một vòng lặp, C++ chạy chưa tới 0,2 giây còn Python mất vài giây.

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ưởnglọc số chẵnLờ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 a \le b \le 2^{26} = 67\,108\,864$.

Test	Nội dung kiểm tra
1–2	Ví dụ đề
3–5	$a = b$: lẻ (đáp án 0) hoặc chẵn
6–10	$a$, $b$ nhỏ với đủ 4 kiểu chẵn / lẻ của hai đầu mút
11–14, 17–18, 20	Đoạn dài tới $2^{26}$: tổng tới $1{,}1 \cdot 10^{15}$, vượt int
15–16, 19	$a$, $b$ lớn nhưng đoạn rất ngắn

Ý tưởngDuyệt và cộng các số chẵn

Biến tong = 0. Cho i chạy từ $a$ tới $b$ (kể cả $b$), nếu i % 2 == 0 thì tong += i.

Có $b - a + 1 \le 6{,}7 \cdot 10^7$ lần lặp: C++ làm khoảng $10^8$ phép tính đơn giản mỗi giây nên vẫn kịp.

Chọn kiểu dữ liệu

Với $a = 1$, $b = 2^{26}$: tổng $= 2 + 4 + \ldots + 2^{26} \approx 1{,}1 \cdot 10^{15}$ – gấp nửa triệu lần giới hạn int → tong phải là long long.

Với Python, vòng lặp $6{,}7 \cdot 10^7$ lần mất vài giây → quá thời gian. Ta dùng công thức tổng cấp số cộng: tìm số chẵn đầu tiên dau $\ge a$ và số chẵn cuối cùng cuoi $\le b$; có so = (cuoi - dau) / 2 + 1 số chẵn, tổng $= \dfrac{(dau + cuoi) \cdot so}{2}$.

Em nhập $a$, $b$ rồi bấm Tiếp để xem vòng lặp xét từng số:

a = b =

Ví dụ nhanh:

Lời giảiC++: vòng lặp – Python: công thức

Bản C++ dùng đúng vòng lặp ở phần ý tưởng. Bản Python dùng công thức tổng cấp số cộng để kịp thời gian.

C++▶ Chạy tay từng dòng codeDuyệt i từ a tới b, cộng các số chẵn vào tổng.

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

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. Biến lặp i cũng khai báo long long cho đồng bộ (thật ra $2^{26}$ vẫn nằm trong int).
2. Có thể cho i nhảy 2 bước để nhanh gấp đôi, nhưng phải bắt đầu từ số chẵn đầu tiên, không phải từ $a$ (xem bẫy "nhảy 2 từ a").
3. Python: nếu dau > cuoi (chỉ xảy ra khi $a = b$ lẻ) thì đoạn không có số chẵn nào, in 0.

Không gian$O(1)$

Thời gian$O(b - a)$ (C++), $O(1)$ (Python)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.162s. Bản Python đúng 20/20 test, chạy lâu nhất 0.065s. 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	13/20	sai test 11, 12, 13, 14, 17, 18, 20
Nhảy 2 bước bắt đầu từ $a$ (khi $a$ lẻ lại cộng các số lẻ)	6/20	sai test 1, 3, 5, 6, 7, 9, 10, 11, 13, 14, 16, 17, 19, 20
Điều kiện lặp i < b (bỏ sót $b$)	8/20	sai test 2, 4, 6, 7, 9, 10, 11, 12, 15, 16, 17, 18
Python: vòng lặp từng số như bản C++	13/20	sai test 11, 12, 13, 14, 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.162s	Full điểm
	Python	20/20	0.065s	Full điểm
Tổng int	C++	13/20	–	Mất 7 test
Nhảy 2 từ a	C++	6/20	–	Mất 14 test
i < b	C++	8/20	–	Mất 12 test
Python vòng lặp	C++	13/20	–	Mất 7 test

Ghi chú của mình: trước khi code hãy ước lượng: bao nhiêu lần lặp (C++ khoảng $10^8$ phép/giây, Python chậm hơn chục lần) và kết quả lớn tới đâu (có vượt int không).

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 😇