Số đặc biệt 2

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản (đề HSG lớp 9, 2024 – 2025) Độ khó: Dễ Đệ quy Số nguyên tố

Đề bài

Một số gọi là số đặc biệt khi tổng các chữ số của nó là một số nguyên tố.

Yêu cầu: nhập một số $N$. Kiểm tra xem $N$ có phải là số đặc biệt hay không. Nếu $N$ là số đặc biệt thì in ra 1, ngược lại in ra 0.

Dữ liệu vào: ghi một số $N$ duy nhất $(0 \le N \le 10^5)$.

Dữ liệu ra: gồm 1 dòng: thông báo kết quả.

Ràng buộc: 80% số test có $0 \le N \le 10^5$; 20% số test không giới hạn.

Ví dụ 1 – input

Ví dụ 1 – output

Ví dụ 2 – input

Ví dụ 2 – output

Ví dụ 3 – input

Ví dụ 3 – output

Giải thích: $14$ có tổng chữ số $1 + 4 = 5$ là số nguyên tố → in 1. $8$ có tổng chữ số 8 không nguyên tố → in 0. $11$ có tổng chữ số $2$ là số nguyên tố → in 1.

Lời mở đầu

Đây là câu 1 (6 điểm) của một đề thi chọn học sinh giỏi lớp 9 môn Tin học năm học 2024 – 2025. Bài gồm 2 việc quen thuộc: tính tổng chữ số và kiểm tra số nguyên tố. Trong chương Đệ quy, mình sẽ viết việc tính tổng chữ số bằng một hàm đệ quy – đây là ví dụ "nhập môn" kinh điển để thấy một bài toán được thu nhỏ dần như thế nào.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test Ý tưởngThu nhỏ n Cách 1Đệ quy trên số Cách 2Đệ quy trên xâu

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	Đáp án 0
1 – 3	14, 8, 11	1 – 2	2	1
4 – 100	2 … 97 817	1 – 5	50	47

Test 1 – 3 là 3 ví dụ của đề. Các test còn lại là số ngẫu nhiên từ 1 đến 5 chữ số, xếp lẫn lộn, hai đáp án 0 và 1 chia gần đều.
Đề ghi "20% số test không giới hạn" nhưng thực tế cả 100 test đều có $N \le 10^5$ (lớn nhất là 97 817), cũng không có test $N = 0$. Nghĩa là chỉ cần một subtask; mình vẫn viết thêm cách 2 đọc xâu để các bạn đi thi thật không bị bất ngờ.

Ý tưởngTổng chữ số = chữ số cuối + tổng chữ số phần còn lại

Với $n \ge 10$: chữ số cuối là $n \bmod 10$, phần còn lại (bỏ chữ số cuối) là $n / 10$. Ví dụ $1234$: chữ số cuối 4, phần còn lại 123. Vậy:

Công thức đệ quy

$\text{tongCS}(n) = n$ nếu $n < 10$ (chỉ còn 1 chữ số – điểm dừng);
$\text{tongCS}(n)$ $= (n \bmod 10) + \text{tongCS}(n / 10)$ nếu $n \ge 10$.

Có tổng $s$ rồi thì kiểm tra nguyên tố: $s \ge 2$ và không có ước nào trong $[2, \sqrt{s}]$. Chú ý $N = 0$ hoặc $N = 10, 100, \dots$ cho tổng 0 hoặc 1 – không phải số nguyên tố.

Em nhập $N$ rồi bấm Tiếp để xem các lời gọi đi xuống, cộng dồn chữ số khi quay lên, rồi kiểm tra nguyên tố:

N =

Ví dụ nhanh:

Cách 1Đọc N là số nguyên – đệ quy trên số

C++▶ Chạy tay từng dòng codeCách 1: tongCS(n) = chữ số cuối + tongCS(n / 10), sau đó kiểm tra nguyên tố.

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

Dữ liệu mẫu:

if(n < 10) return n; là điểm dừng. Nhờ điều kiện này mà $N = 0$ cũng chạy đúng (trả về 0) chứ không đệ quy mãi.
Mỗi lời gọi bỏ đi 1 chữ số, nên số lời gọi bằng số chữ số của $N$ (tối đa 6 với $N \le 10^5$).
Hàm nguyenTo dùng điều kiện i * i <= x; tổng chữ số rất nhỏ (tối đa 45 với $N < 10^5$) nên vòng lặp chỉ vài bước.

Không gian$O(d)$ – độ sâu đệ quy, $d$ là số chữ số

Thời gian$O(d + \sqrt{s})$, $s$ là tổng chữ số

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.004 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.029 giây.

Cách 2Phòng khi N "không giới hạn" – đọc N là xâu

Đề nói 20% test "không giới hạn". Nếu $N$ thật sự có hàng trăm chữ số thì không kiểu số nguyên nào chứa nổi, nên ta đọc $N$ dạng xâu và đệ quy theo vị trí: tổng các chữ số từ vị trí $i$ đến hết = chữ số thứ $i$ + tổng từ vị trí $i + 1$. Điểm dừng là khi $i$ chạy hết xâu (tổng bằng 0).

C++▶ Chạy tay từng dòng codeCách 2: đọc N dạng xâu, đệ quy theo vị trí i.

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

Dữ liệu mẫu:

s[i] - '0' đổi ký tự chữ số thành giá trị số (ví dụ '7' - '0' = 7).
Độ sâu đệ quy bằng độ dài xâu. Với xâu vài trăm nghìn chữ số thì C++ vẫn ổn, còn Python phải tăng sys.setrecursionlimit (mình đặt sẵn) và có thể tràn ngăn xếp nếu xâu quá dài – khi đó dùng vòng lặp sẽ an toàn hơn.

Không gian$O(d)$ – xâu và ngăn xếp đệ quy

Thời gian$O(d + \sqrt{s})$

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.004 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.032 giây.

Ghi chú của mình: cả 2 cách (C++ lẫn Python) đều đúng 100/100 test, mỗi test chạy dưới 0.005 giây (C++). Đi thi thật, nếu đề ghi "không giới hạn" mà không nói rõ giới hạn thì các bạn nên đọc $N$ dạng xâu như cách 2 cho chắc ă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 😇

Lập Trình Thuật Toán