GSUM
Đề bài
Ta gọi GSUM của một số nguyên dương $n$ là lặp lại tính tổng các chữ số của $n$ cho đến khi nào tổng các chữ số chỉ còn lại đúng 1 chữ số thì dừng. Ví dụ:
- $GSUM(153) = 1 + 5 + 3 = 9$.
- $GSUM(2244)$ $= 2 + 2 + 4 + 4$ $= 12 \to 1 + 2$ $= 3$.
Nhiệm vụ của bài tập này là xây dựng chương trình con đệ quy tính GSUM của một số nguyên dương $n$ được nhập vào từ bàn phím.
Dữ liệu vào:
- Gồm số nguyên dương $n$ $(0 \le n \le 10^{18})$.
Kết quả:
- In một số nguyên duy nhất là đáp án của bài toán.
153922443Lời mở đầu
Bài này có hai tầng đệ quy lồng nhau: tính tổng chữ số đã là một bài đệ quy, và việc "cộng tiếp cho tới khi còn 1 chữ số" lại là một tầng đệ quy nữa. Thêm một cái bẫy nhỏ: $n$ lên tới $10^{18}$, dùng int là tràn số ngay. Cuối bài mình tặng thêm một công thức $O(1)$ rất gọn dựa trên phép chia cho 9. Bài thuộc chương Đệ quy cơ bản trên CLUE OJ (nguồn bài: VinhDinhCoder).
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, mỗi test là một số $n$:
| Test | n | Số chữ số | Đáp án |
|---|---|---|---|
| 1–30 | 111 … 525.095.703 | 3 … 9 | 1, 2, 3, 4, 5, 6, 7, 8, 9 |
| 31–70 | 2.494.215.876 … 821.034.825.241.424 | 10 … 15 | 1, 2, 3, 4, 5, 6, 7, 8, 9 |
| 71–100 | 1.357.911.167.972.809 … 986.435.618.980.070.892 | 16 … 18 | 3, 4, 5, 6, 7, 8, 9 |
- Test 1–30: $n$ tối đa khoảng $5 \cdot 10^8$ – vẫn vừa kiểu
int. - Test 31–70: $n$ có 10 tới 15 chữ số; test 71–100: $n$ có 16 tới 18 chữ số – bắt buộc dùng
long long. - Không có test $n = 0$ (code bên dưới vẫn in đúng $0$).
Đề không chia subtask, mình chia 3 nhóm theo độ lớn của $n$ để thấy rõ cái bẫy kiểu dữ liệu (kết quả chạy thật, giới hạn 1 giây):
| Nhóm | Điều kiện | Test | Dùng int(code sai) | Cách 1 (đệ quy) | Cách 2 (công thức) |
|---|---|---|---|---|---|
| 1 | $n < 2^{31}$ (vừa kiểu int) | 1–30 | 30/30 | 30/30 | 30/30 |
| 2 | $n \le 10^{15}$ | 31–70 | 4/40 | 40/40 | 40/40 |
| 3 | $n \le 10^{18}$ | 71–100 | 0/30 | 30/30 | 30/30 |
Ý tưởngHai hàm đệ quy lồng nhau
Hàm 1 – tổng chữ số sumDigit(n): chữ số cuối của $n$ là n % 10, phần còn lại (bỏ chữ số cuối) là n / 10. Vậy:
Hàm 2 – GSUM: nếu $n$ đã chỉ có 1 chữ số thì xong; ngược lại thay $n$ bằng tổng chữ số của nó rồi làm tiếp:
Hàm gsum gọi sumDigit trước, lấy kết quả rồi mới gọi lại chính nó. Em nhập $n$ rồi bấm Tiếp để xem ngăn xếp lời gọi của cả hai hàm:
Hàm gsum gọi lại chính nó rất ít lần: $n \le 10^{18}$ có tối đa 19 chữ số nên tổng chữ số $\le 9 \cdot 19 = 171$, lần sau còn $\le 1 + 9 + 9 = 19$, rồi $\le 10$, rồi xong.
Cách 1Cài đặt đệ quy – $O(\text{số chữ số})$
- Tham số và giá trị trả về đều là
long longvì $n \le 10^{18}$ vượt xa giới hạn củaint(khoảng $2{,}1 \cdot 10^9$). Mình đã thử bản dùngint: chỉ đúng 34/100 test – sai gần hết các test có $n \ge 2^{31}$ (vài test đúng do may mắn). - Điểm dừng của cả hai hàm đều là
n < 10. Với $n = 0$ hàm trả về 0 ngay. gsum(sumDigit(n)): máy tínhsumDigit(n)xong (toàn bộ chuỗi lời gọi của nó đã kết thúc) rồi mới gọigsumvới kết quả đó.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.00s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.02s.
Cách 2Công thức chia cho 9 – $O(1)$
Vì $10 \equiv 1 \pmod 9$ nên một số và tổng các chữ số của nó luôn có cùng số dư khi chia cho 9 (đây là dấu hiệu chia hết cho 9 các bạn đã học). Cộng chữ số bao nhiêu lần thì số dư vẫn giữ nguyên, và kết quả cuối là một số từ 1 đến 9 (khi $n > 0$). Do đó:
Thử lại: $153 = 9 \cdot 17$ chia hết cho 9 → đáp án 9 ✓. $2244 = 9 \cdot 249 + 3$ → đáp án 3 ✓.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.02s. Cách này không dùng đệ quy nên bài nộp theo đúng yêu cầu chương thì các bạn dùng cách 1 nhé; cách 2 dùng để kiểm tra chéo và để nhớ một tính chất số học rất hay.
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ú |
|---|---|---|---|---|
Đệ quy nhưng dùng int | C++ | 34/100 | 0.00s | Tràn số khi n ≥ 231 |
| 1. Hai hàm đệ quy (long long) | C++ | 100/100 | 0.00s | Full điểm |
| Python | 100/100 | 0.02s | Full điểm | |
| 2. Công thức 1 + (n − 1) mod 9 | C++ | 100/100 | 0.01s | Full điểm |
| Python | 100/100 | 0.02s | Full điểm |
int – chỉ đúng khoảng một phần ba số test. Đáp án trong bộ test chỉ là các số từ 1 đến 9.