P194SUMH - Tích các chữ số

Đọc đề bài trên PTIT SPOJ

Đề bài

Cho số nguyên $n$, tìm số nguyên dương $x$ nhỏ nhất sao cho tích các chữ số của $x$ bằng $n$ (giả sử $x = \overline{abcd}$ thì $n = a\times b \times c \times d$). Nếu không tồn tại số $x$ nào thì in ra $-1$.

Điều kiện

• $0 \leq n \leq 600$

Giải

Nếu $n \in (0, 10)$ thì $x = n$. VD: $n = 9$ thì $x$ có thể là $9, 19, 91, 119, 191, ..$ và ta lấy $9$ là số nhỏ nhất, từ đây tự hiểu các số trong $(0, 10)$.

Nếu $n \in [10, 600]$ thì Algoritham - chia $n$ lần lượt cho các số từ $9$ đến $2$, nếu cuối cùng không ra $1$ thì kết luận không đổi được. Một cách làm khác là có thể tính tích chữ số của từng số trong đoạn $[11, 12345]$ rồi lấy số đầu tiên thỏa yêu cầu.

• Giải thích thêm chỗ này: ta đặt câu hỏi là cần bao nhiêu chữ số tối thiểu để tích các chữ số đó bằng $600$? Ta có thể thử lấy cận trên $x_{\text{max}} = 123456$, khi đó tích các chữ số $n_{\text{xmax}} = 720 > 600$. Với cận trên $x_{\text{max}}$ này ta có thể trâu giá trị $n = 600$ và thu được $x = 3558$. Giờ thử giảm $x_{\text{max}} = 12345$, ta vẫn có thể trâu $n = 600, x = 3558$. Ta không thể giảm xuống $1234$ được nữa, vì $1234 < 3558$.
  
  Khi đó ta tạm "hình dung" là $x$ có tối đa $4$ chữ số, từ đây ta nghĩ tới chuyện trâu trong đoạn $[11, 12345]$!.

Đặc biệt chú ý điều kiện $n = 0$, khi đó $x = 10$. Đề yêu cầu tìm số nguyên dương và $0$ không phải là một số nguyên dương!

Đây là code mẫu

Nhận xét

Đây vẫn không phải là một bài toán khó, duyệt trâu vẫn AC. Chỉ cần chú ý đọc kỹ điều kiện là ổn :/

Happy coding!