Đếm chẵn chia hết cho 3

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Đếm bằng công thức

Đề bài

Cho hai số nguyên dương $a$ và $b$. Hãy đếm xem trong đoạn $[a, b]$ (tính cả $a$ và $b$) có bao nhiêu số chẵn và chia hết cho 3.

Dữ liệu vào:

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

Kết quả:

In ra một số nguyên là số lượng số chẵn chia hết cho 3 trong đoạn $[a, b]$.

Giới hạn:

• $1 \le a \le b \le 10^{10}$

Subtask:

• Subtask 1 (40% số điểm): $b \le 10^6$.
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm.

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

50 8444321

Ví dụ 1 – output

1407378

Ví dụ 2 – input

6 12

Ví dụ 2 – output

2

• Ví dụ 1: các số cần đếm là $54, 60, 66, \ldots, 8444316$, có tất cả $1407378$ số.
• Ví dụ 2: có hai số $6$ và $12$ (hai đầu mút cũng được tính).

Nguồn: phỏng theo bài "ĐẾM CHẴN" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Đếm số thoả điều kiện trong một đoạn – việc quen thuộc của vòng lặp. Nhưng đoạn ở đây dài tới $10^{10}$ số: duyệt từng số sẽ chạy mất cả chục giây. Bài này dạy em khi nào nên bỏ vòng lặp và đếm bằng phép chia. Ghi chú: đề gốc viết "trong đoạn (a, b)" giống ký hiệu khoảng mở, nhưng ví dụ $50, 8444321 \to 1407378$ chỉ khớp khi tính cả hai đầu $a, b$, nên mình chốt đoạn $[a, b]$ và ghi rõ trong đề.

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ưởngbội của 6Lờ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. Test 1–8 thuộc subtask 1 ($b \le 10^6$), test 9–20 có $b$ tới $10^{10}$.

Test	Nội dung kiểm tra
1–8	Đoạn nhỏ: một số duy nhất, hai đầu mút là bội của 6 (bắt lỗi khoảng mở), đoạn không có số nào, tới $10^6$
9	Ví dụ 1 của đề
10–12, 14–16, 20	Đoạn dài hàng tỉ số (tới $10^{10}$) – duyệt từng số bị quá thời gian
11, 13, 17–19	Đầu mút là bội của 6 cỡ $10^{10}$, quanh $2^{31}$ và $2^{32}$ – int bị tràn, khoảng mở bị sai

Ý tưởngĐếm bội của 6 bằng phép chia

Số chẵn (chia hết cho 2) và chia hết cho 3 ⇔ chia hết cho 6. Cách tự nhiên nhất là vòng lặp:

for (i = a; i <= b; i++) if (i % 6 == 0) dem++;

Cách này đúng và đủ cho subtask 1 ($b \le 10^6$), nhưng với $b = 10^{10}$ máy phải chạy $10^{10}$ vòng – khoảng chục giây, trong khi giới hạn chỉ 1 giây.

Đếm bằng phép chia

Trong đoạn $[1, n]$ có đúng $\lfloor n / 6 \rfloor$ bội của 6 (là $6, 12, \ldots$). Vậy số bội của 6 trong $[a, b]$ bằng số bội trong $[1, b]$ trừ đi số bội trong $[1, a - 1]$:

$\text{đáp án} = \lfloor b / 6 \rfloor - \lfloor (a - 1) / 6 \rfloor$

Chú ý là $a - 1$ chứ không phải $a$ – nếu trừ $\lfloor a/6 \rfloor$ thì $a$ bị loại khỏi phép đếm.

Em nhập $a, b$ rồi bấm Tiếp: mô phỏng duyệt thử vài số đầu, sau đó dùng công thức:

a = b =

Ví dụ nhanh:

Lời giảiMột phép trừ hai phép chia

Mọi biến là long long vì $a, b$ tới $10^{10}$ – vượt int.

C++▶ Chạy tay từng dòng codeĐếm bội của 6 trong [a, b] bằng công thức.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phép / giữa hai số nguyên trong C++ là chia nguyên (bỏ phần dư) – đúng thứ ta cần để đếm. Python dùng //.
2. Vì $a \ge 1$ nên $a - 1 \ge 0$, không phải lo chia số âm.
3. Muốn kiểm tra công thức, em có thể viết thêm bản vòng lặp rồi so kết quả trên các đoạn nhỏ.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.026s. 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ú
Duyệt từng số từ $a$ tới $b$ (for + %)	13/20	sai test 10, 11, 12, 14, 15, 16, 20
Dùng int	10/20	sai test 10, 11, 12, 13, 15, 16, 17, 18, 19, 20
Hiểu là khoảng mở $(a, b)$: (b - 1)/6 - a/6	11/20	sai test 2, 3, 4, 6, 8, 11, 13, 16, 17
Trừ a/6 thay vì (a - 1)/6	12/20	sai test 2, 3, 6, 8, 11, 13, 16, 17

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.004s	Full điểm
	Python	20/20	0.026s	Full điểm
Duyệt từng số	C++	13/20	–	Mất 7 test
Dùng int	C++	10/20	–	Mất 10 test
Khoảng mở	C++	11/20	–	Mất 9 test
Mất đầu a	C++	12/20	–	Mất 8 test

Ghi chú của mình: vòng lặp là công cụ chứ không phải đích đến. Khi số vòng lên tới $10^9$ trở lên, hãy tìm công thức – "đếm bội của $k$ trong $[a, b]$" là công thức sẽ gặp lại rất nhiều lần.

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 😇