Số đặc biệt (chia hết tổng chữ số)

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Tách chữ số

Đề bài

Một số nguyên dương $n$ được gọi là số đặc biệt nếu $n$ chia hết cho tổng các chữ số của nó. Ví dụ $27$ là số đặc biệt vì $27$ chia hết cho $2 + 7 = 9$; còn $11$ không phải số đặc biệt vì $11$ không chia hết cho $1 + 1 = 2$.

Cho số nguyên dương $n$, hãy kiểm tra $n$ có phải số đặc biệt hay không.

Dữ liệu vào:

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

Kết quả:

In ra 1 nếu $n$ là số đặc biệt, ngược lại in ra 0.

Giới hạn:

• $1 \le n \le 10^{18}$

Subtask:

• Subtask 1 (50% số điểm): $n \le 10^9$.
• Subtask 2 (50% 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

27

Ví dụ 1 – output

1

Ví dụ 2 – input

11

Ví dụ 2 – output

0

• Ví dụ 1: tổng chữ số $2 + 7 = 9$, $27 = 9 \cdot 3$ nên in $1$.
• Ví dụ 2: tổng chữ số $1 + 1 = 2$, $11$ lẻ nên không chia hết cho $2$, in $0$.

Nguồn: phỏng theo bài "SỐ ĐẶC BIỆT" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Bài luyện kỹ thuật quan trọng nhất của chương vòng lặp: tách các chữ số của một số bằng % 10 và / 10. Hai cái bẫy: $n$ tới $10^{18}$ (phải long long), và nếu tách chữ số trực tiếp trên $n$ thì đến lúc chia, $n$ đã thành $0$ mất rồi! Ghi chú: đề gốc không có subtask; mình thêm subtask $n \le 10^9$ (50%) để bạn nào dùng int vẫn có điểm.

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ưởng% 10 và / 10Lờ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–10 thuộc subtask 1 ($n \le 10^9$), test 11–20 có $n$ tới $10^{18}$.

Test	Nội dung kiểm tra
1–10	Số nhỏ: ví dụ đề, $n = 1$, $10$, $100$, $10^9$, $999\,999\,999$; cả đáp án 1 và 0
11–14, 17–18	Số cỡ $10^{18}$: vượt int, và lớn hơn $2^{53}$ nên double làm tròn sai chữ số cuối
15–16, 19	Quanh ranh giới int: $2^{31} - 1$, $2^{31}$, $3 \cdot 10^9 + 6$
20	$2^{53} + 31$: chỉ lớn hơn $2^{53}$ một chút nhưng double đã không lưu chính xác

Ý tưởngTách chữ số trên một bản sao

Với số nguyên dương $x$:

• x % 10 là chữ số cuối của $x$ (ví dụ $1234 \% 10 = 4$);
• x / 10 (chia nguyên) là $x$ bỏ đi chữ số cuối ($1234 / 10 = 123$).

Lặp "lấy chữ số cuối cộng vào tổng, rồi bỏ chữ số cuối" chừng nào $x > 0$ là được tổng các chữ số $s$. Cuối cùng kiểm tra n % s == 0.

Đừng phá n!

Vòng lặp chia $x$ cho 10 tới khi $x = 0$. Nếu làm trực tiếp trên $n$ thì sau vòng lặp $n = 0$ và 0 % s luôn bằng 0 → mọi số đều thành "đặc biệt". Hãy sao chép x = n rồi tách chữ số trên $x$.

$n \le 10^{18}$ có tối đa 19 chữ số nên vòng lặp chạy tối đa 19 lần.

Em nhập $n$ rồi bấm Tiếp để xem từng chữ số được tách ra:

n =

Ví dụ nhanh:

Lời giảiVòng while tách chữ số

Đọc $n$ vào long long, tách chữ số trên bản sao $x$.

C++▶ Chạy tay từng dòng codeTính tổng chữ số bằng % 10 và / 10, rồi kiểm tra chia hết.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. s không vượt quá $9 \cdot 19 = 171$ nhưng để chung kiểu long long cho gọn.
2. Vì $n \ge 1$ nên $s \ge 1$, không bao giờ chia cho 0.
3. Python: số nguyên không giới hạn nên không lo tràn, nhưng nhớ dùng // chứ không phải / (phép / ra số thực).

Không gian$O(1)$

Thời gian$O(\text{số chữ số})$ – tối đa 19 vòng

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.006s. Bản Python đúng 20/20 test, chạy lâu nhất 0.024s. 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ách chữ số trực tiếp trên $n$, rồi mới kiểm tra n % s	13/20	sai test 4, 5, 8, 12, 13, 15, 16
Đọc $n$ vào int	14/20	sai test 11, 14, 17, 18, 19, 20
Đọc $n$ vào double rồi ép sang long long	14/20	sai test 12, 13, 14, 17, 18, 20
Điều kiện lặp x >= 10 (sót chữ số đầu tiên)	12/20	sai test 1, 4, 8, 10, 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.006s	Full điểm
	Python	20/20	0.024s	Full điểm
Phá n	C++	13/20	–	Mất 7 test
Dùng int	C++	14/20	–	Mất 6 test
Dùng double	C++	14/20	–	Mất 6 test
Sót chữ số đầu	C++	12/20	–	Mất 8 test

Ghi chú của mình: mẫu "while (x > 0) { … x % 10 …; x /= 10; }" sẽ theo em suốt các bài về chữ số. Nhớ luôn làm trên bản sao nếu sau đó còn cần dùng lại số ban đầu.

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 😇