Tính toán (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B)

Nguồn: Tin học trẻ 2025 – Vòng loại QG đợt 1 – Bảng B Độ khó: Dễ Toán Chia hết cho 9

Đề bài

Mình gọi một số nguyên dương là số đẹp nếu tổng các chữ số của nó chia hết cho $9$. Ví dụ $9$ (tổng chữ số $9$), $18$ ($1 + 8 = 9$), $2007$ ($2 + 0 + 0 + 7 = 9$) đều là số đẹp, còn $20$ ($2 + 0 = 2$) thì không.

Cho số nguyên dương $n$. Hãy tính tổng của tất cả các số đẹp không vượt quá $n$.

Dữ liệu vào: một dòng chứa số nguyên dương $n$ $(n \le 10^9)$.

Kết quả: một dòng chứa một số nguyên là tổng tính được.

Subtask:

• Subtask 1 (80% số test): $n \le 10^6$.
• Subtask 2 (20% số test): không có ràng buộc gì thêm.

Giới hạn thời gian: 0,1 giây (rất chặt!), bộ nhớ: 1 GB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 1 – Bảng B. Đề được mình viết lại cho dễ đọc.

Ví dụ – input

20

Ví dụ – output

27

Giải thích: các số đẹp không vượt quá $20$ là $9$ và $18$, tổng bằng $9 + 18 = 27$.

Lời mở đầu

Bài mở màn của vòng loại đợt 1 bảng B: đề rất ngắn, cách "trâu" thì ai cũng nghĩ ra ngay – duyệt từng số, tính tổng chữ số. Nhưng giới hạn thời gian chỉ 0,1 giây và $n$ lên tới $10^9$ nên muốn trọn điểm thì phải nhìn ra một tính chất quen thuộc từ lớp 6: dấu hiệu chia hết cho 9. Mình sẽ đi 3 bước: duyệt trâu (ăn subtask 1) → chỉ duyệt các bội của 9 → công thức tính ngay.

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 9Cách 1duyệt trâuCách 2bước nhảy 9Cách 3công thức O(1)Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE gồm 20 test (mình tự sinh theo đúng ràng buộc của đề), mỗi test chỉ là một số $n$. Test 1 là ví dụ của đề; test 1–16 thoả $n \le 10^6$ (subtask 1), test 17–20 có $n$ tới $10^9$ (subtask 2). Lời giải cuối cùng (cách 3) mình đã nộp thử trên bộ chấm chính thức của tinhoctre.vn và được 100 điểm.

Nhóm	Test	$n$ nhỏ nhất	$n$ lớn nhất	Đáp án lớn nhất	Số test $n < 9$ (đáp án 0)
Subtask 1	1–16	1	1.000.000	55.555.944.444	2
Subtask 2	17–20	187.063.046	1.000.000.000	55.555.555.944.444.444	0

• Có các test biên nhỏ: $n = 1$, $n = 8$ (chưa có số đẹp nào → in $0$), $n = 9, 10, 17, 18$ (ngay sát các bội của 9).
• Đáp án lớn nhất khoảng $5{,}6 \cdot 10^{16}$ – vượt xa kiểu int nên phải dùng long long.

Kết quả chạy thật của các cách bên dưới theo từng subtask (thời gian CPU, giới hạn 0,1s):

Subtask	Điều kiện	Test	Cách 1 C++	Cách 2 C++	Cách 2 Python	Cách 3 C++ / Python
Subtask 1 (80%)	$n \le 10^6$	1–16	16/16	16/16	16/16	16/16
Subtask 2 (20%)	không có ràng buộc gì thêm ($n \le 10^9$)	17–20	0/4	4/4	0/4	4/4

Ý tưởngSố đẹp chính là bội của 9

Viết số $v$ dưới dạng các chữ số $v = \overline{c_k \dots c_1 c_0}$ $= c_k \cdot 10^k + \dots + c_1 \cdot 10 + c_0$. Vì $10 = 9 + 1$ nên $10^i$ chia 9 luôn dư 1, do đó

$$v \equiv c_k + \dots + c_1 + c_0 \pmod 9.$$

Nhận xét then chốt

Một số và tổng các chữ số của nó có cùng số dư khi chia cho 9. Vậy "tổng chữ số chia hết cho 9" ⇔ "số đó chia hết cho 9". Các số đẹp không vượt quá $n$ chính là $9, 18, 27, \dots, 9k$ với $k = \lfloor n / 9 \rfloor$.

Em nhập $n$ rồi bấm Tiếp để xem từng số được kiểm tra: số nhỏ phía trên mỗi ô là tổng chữ số, ô xanh là số đẹp – để ý chúng cách đều nhau đúng 9 đơn vị:

n =

Ví dụ nhanh:

Cách 1Duyệt từng số, tính tổng chữ số – O(n log n)

Làm đúng như đề nói: với mỗi $v$ từ $1$ đến $n$, tách từng chữ số bằng % 10 và / 10, cộng lại; nếu tổng chia hết cho 9 thì cộng $v$ vào đáp án.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi số từ 1 đến n, tách chữ số để tính tổng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng while(t > 0) lấy chữ số cuối t % 10 rồi bỏ nó đi bằng t /= 10 – mỗi số tốn khoảng 7–10 vòng.
2. ans phải là long long: với $n = 10^6$ tổng đã khoảng $5{,}6 \cdot 10^{10}$.

Không gian$O(1)$

Thời gian$O(n \cdot \text{số chữ số})$

Kết quả chạy thật: bản C++ đúng 16/20 test, quá thời gian test 17–20 (các test đúng chạy lâu nhất 0.009s). Toàn bộ subtask 1 qua, 4 test của subtask 2 ($n$ cỡ $10^9$, gần $10^{10}$ phép tính) bị quá thời gian. Bản Python đúng 8/20 test, quá thời gian test 8–11, 13–20 (các test đúng chạy lâu nhất 0.082s) – Python chậm hơn C++ khoảng 50 lần nên với giới hạn 0,1s chỉ qua được các test $n$ nhỏ.

Cách 2Chỉ duyệt các bội của 9 – O(n/9)

Nhờ nhận xét ở trên, ta không cần tính tổng chữ số nữa: chỉ cần cộng các số $9, 18, 27, \dots$ không vượt quá $n$. Số vòng lặp giảm còn $n / 9 \approx 1{,}1 \cdot 10^8$ khi $n = 10^9$.

C++▶ Chạy tay từng dòng codeCách 2: chỉ duyệt các bội của 9.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(n / 9)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.066s. Qua hết nhưng test lớn nhất mất cỡ 0,066s – sát giới hạn 0,1s, máy chấm chậm hơn một chút là có thể bị quá giờ. Bản Python đúng 16/20 test, quá thời gian test 17–20 (các test đúng chạy lâu nhất 0.035s): $10^8$ vòng lặp là quá sức với Python.

Cách 3Công thức cấp số cộng – O(1)

Đặt $k = \lfloor n / 9 \rfloor$ là số bội của 9 không vượt quá $n$. Tổng cần tính là

$$9 + 18 + \dots + 9k = 9 \cdot (1 + 2 + \dots + k) = 9 \cdot \frac{k(k+1)}{2}.$$

Thử với ví dụ: $n = 20$ → $k = 2$ → $9 \cdot \frac{2 \cdot 3}{2} = 27$ ✔.

C++▶ Chạy tay từng dòng codeCách 3: công thức 9·k(k+1)/2 với k = n / 9.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Tính k * (k + 1) / 2 trước rồi mới nhân 9: $k(k+1)$ luôn chẵn nên phép chia 2 không bị làm tròn, và kết quả trung gian nhỏ hơn.
2. Với $n = 10^9$: $k = 111\,111\,111$, $k(k+1) \approx 1{,}2 \cdot 10^{16}$ vẫn vừa long long (giới hạn khoảng $9{,}2 \cdot 10^{18}$).

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.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.023s. Full điểm, và đây cũng là lời giải mình đã nộp trên tinhoctre.vn (100 điểm).

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ú
1. Duyệt từng số, tính tổng chữ số	C++	16/20	0.009s	quá giờ 17–20 – ăn subtask 1
	Python	8/20	0.082s	quá giờ 8–11, 13–20
2. Chỉ duyệt bội của 9	C++	20/20	0.066s	Đúng hết – sát giới hạn 0,1s
	Python	16/20	0.035s	quá giờ 17–20
3. Công thức $O(1)$	C++	20/20	0.003s	Đúng hết
	Python	20/20	0.023s	Đúng hết

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình với giới hạn 0,1 giây. Cách 1 ăn trọn subtask 1 (80% số test); cách 2 qua hết nhưng sát nút; cách 3 chạy tức thì với cả C++ và Python. Bài học: khi thấy "tổng chữ số chia hết cho 9" hãy nghĩ ngay tới dấu hiệu chia hết – một nhận xét nhỏ biến bài $10^9$ phép tính thành 3 phép tính.

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 😇