Mã Hóa Đại Hiệp (MAHOA

Nguồn: ICTU 8 Độ khó: Trung bình Tham lam Số học Phân tích thừa số

Đề bài

MAHOA

Điểm số: 1. Giới hạn thời gian: 1s. Giới hạn bộ nhớ: 512 MB. Người đăng: admin.

Đại Hiệp đang học môn An toàn bảo mật thông tin, có rất nhiều quy tắc để mã hoá dữ liệu hay, tuy nhiên Đại Hiệp rất muốn phát minh ra một quy tắc mã hoá để đời, lưu danh sử sách đúng với cái tên Đại Hiệp.

Sau vài ngày suy nghĩ, Đại Hiệp quyết định chọn một quy tắc thật khó và đặt tên là mã hoá Đại Hiệp.

Nội dung quy tắc: Với một số nguyên dương $X$ sẽ được mã hoá sang một số nguyên dương $Y$ sao cho tích các chữ số của $Y$ bằng với $X$ và $Y$ là số nguyên dương bé nhất.

Tuy nhiên sau khi đặt ra quy tắc mã hoá này, Đại Hiệp thấy thật là khó để tìm số mã hoá. Bạn hãy giúp Đại Hiệp tìm số mã hoá đó.

Đầu vào: Số nguyên $X$ $(0 \le X \le 10^9)$.

Đầu ra: Số nguyên dương được mã hoá với quy tắc Đại Hiệp. Nếu không thể tìm thấy số nào, hãy in ra $-1$.

Ví dụ – input

12

Ví dụ – output

26

Giải thích: ta có $2 \cdot 6 = 12$ ⇒ $26$ là phù hợp và nó cũng là số bé nhất tìm được.

Lời mở đầu

Có bạn nhắn tin hỏi mình bài tập này, mình thấy cũng thú vị nè nên viết bài giải để anh em thử sức và tham khảo luôn 😇. Bài này đọc đề thì dễ bị "tẩu hoả nhập ma", nghĩ theo hướng phức tạp (lúc đầu mình cũng vậy 😅), nhưng thật ra chỉ cần một nhận xét tham lam nhỏ là đủ.

Giải thích ví dụ cho bạn nào chưa hiểu đề: với $X = 12$, ta cần tìm số $Y$ nhỏ nhất mà nhân các chữ số của nó lại được $12$. Các số có tích chữ số bằng 12 là $26$ ($2 \cdot 6$), $34$ ($3 \cdot 4$), $43$, $62$, $126$ ($1 \cdot 2 \cdot 6$), $223$ ($2 \cdot 2 \cdot 3$), ... Nhỏ nhất là 26. Còn với $X = 11$ thì không có chữ số nào (từ 0 đến 9) chia hết cho 11, nên không thể tạo ra tích bằng 11 ⇒ in $-1$.

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 để nhảy tới:

Cách 1Tham lam: tách chữ số từ 9 về 2 rồi xếp tăng dần · O(log X)

Cách 1Tham lam: tách chữ số từ 9 về 2 – O(log X)

Vì sao không duyệt Y từ 1 trở lên?

Cách "ngây thơ" là thử $Y = 1, 2, 3, \ldots$ rồi tính tích chữ số cho tới khi gặp $X$. Nhưng đáp án có thể rất lớn: ví dụ $X = 10^9 = 2^9 \cdot 5^9$ thì đáp án là $555555555888$ (12 chữ số) ⇒ duyệt tới đó là không tưởng. Hơn nữa nếu không có đáp án thì vòng lặp chạy mãi không dừng. Ta phải xây đáp án trực tiếp.

Hai trường hợp đặc biệt

• $X = 0$: tích chữ số bằng 0 khi $Y$ có ít nhất một chữ số $0$. Mà $Y$ phải dương nên không thể là số $0$, số dương nhỏ nhất có chữ số 0 là 10.
• $1 \le X \le 9$: bản thân $X$ là một chữ số, tích chữ số của nó chính là $X$, và không số dương nào nhỏ hơn $X$ có tích chữ số bằng $X$ (các số nhỏ hơn đều có 1 chữ số, tích là chính nó). Đáp án là $X$. (Riêng $X = 1$ ⇒ $Y = 1$.)

Trường hợp X ≥ 10: tham lam

Khi $X \ge 10$, $Y$ chắc chắn có từ 2 chữ số trở lên, và trong $Y$ không nên có chữ số $1$ (bỏ chữ số 1 đi thì tích không đổi mà số ngắn hơn ⇒ nhỏ hơn), cũng không có chữ số $0$ (tích sẽ bằng 0). Vậy $Y$ chỉ gồm các chữ số từ $2$ đến $9$, tích của chúng bằng $X$. Có 2 nhận xét:

1. Càng ít chữ số càng tốt: số có ít chữ số hơn thì luôn nhỏ hơn. Muốn ít chữ số thì mỗi chữ số phải "gánh" được càng nhiều thừa số càng tốt ⇒ ưu tiên tách các chữ số lớn trước: chia $X$ cho $9$ được bao nhiêu lần thì chia hết, rồi tới $8$, $7$, $6$, ..., cuối cùng là $2$.
2. Đã có các chữ số thì xếp tăng dần: cùng một bộ chữ số, xếp chữ số nhỏ lên đầu sẽ được số nhỏ nhất. Vì ta tách từ 9 về 2 nên chuỗi thu được đang giảm dần ⇒ chỉ cần đảo ngược lại.

Sau khi chia hết cho các chữ số từ 9 về 2 mà $X$ vẫn còn lớn hơn 1, nghĩa là $X$ có một thừa số nguyên tố lớn hơn 7 (như 11, 13, ...) mà không chữ số nào chứa được ⇒ in $-1$.

Thuật toán

s = ""; với $d = 9, 8, \ldots, 2$: trong khi $X$ chia hết cho $d$ thì thêm chữ số $d$ vào s và $X = X / d$.
Cuối cùng: nếu $X \ne 1$ ⇒ $-1$; ngược lại đáp án là s đảo ngược (các chữ số tăng dần).

Vì sao tách 9 trước 8, 8 trước 6...?

Ví dụ $X = 72 = 2^3 \cdot 3^2$. Tham lam: chia 9 ⇒ còn 8, chia 8 ⇒ còn 1 ⇒ chữ số $\{9, 8\}$ ⇒ 89. Nếu tách 6 trước: $72 = 6 \cdot 12 = 6 \cdot 6 \cdot 2$ ⇒ $266$ (3 chữ số, lớn hơn). Hai số 3 gộp thành một chữ số 9 và ba số 2 gộp thành một chữ số 8 là gọn nhất. Một vài so sánh khác:

X	Tham lam (9 → 2)	Một cách tách khác
12	6·2 ⇒ 26	4·3 ⇒ 34
48	8·6 ⇒ 68	6·4·2 ⇒ 246
100	5·5·4 ⇒ 455	5·5·2·2 ⇒ 2255
360	9·8·5 ⇒ 589	8·5·3·3 ⇒ 3358

Bài toán này là dạng kinh điển, cách tham lam chia từ 9 về 2 luôn cho số chữ số ít nhất, và trong các cách có cùng số chữ số thì cho bộ chữ số xếp lên nhỏ nhất. Mình cũng đã kiểm tra lại bằng code vét cạn (xem ghi chú cuối bài).

Đáp án vượt int, và đừng quên X = 0

Đáp án có thể có tới 13 chữ số (ví dụ $10^9 \to 555555555888$), vượt xa int. Code của mình ghép đáp án vào một xâu rồi in ra nên không lo tràn số. Ngoài ra nhớ xử lý riêng $X = 0$ (đáp án 10) và $X \lt 10$ – nếu không, vòng tham lam với $X = 0$ sẽ lặp vô hạn (vì $0$ chia hết cho mọi $d$), còn với $X = 1$ sẽ ra xâu rỗng.

Minh hoạ

Em nhập $X$ rồi bấm Tiếp để xem từng lần chia: hàng ô trên là các chữ số $d$ đang thử (từ 9 về 2), hàng dưới là các chữ số đã tách được:

X

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x;
    cin >> x;
    if (x == 0) {               // cần một chữ số 0, số dương nhỏ nhất là 10
        cout << 10;
        return 0;
    }
    if (x < 10) {               // bản thân x là một chữ số
        cout << x;
        return 0;
    }
    string s = "";
    for (int d = 9; d >= 2; d--) {
        while (x % d == 0) {    // tách chữ số lớn trước
            s += char('0' + d);
            x /= d;
        }
    }
    if (x != 1) {               // còn thừa số nguyên tố > 7
        cout << -1;
        return 0;
    }
    reverse(s.begin(), s.end());    // chữ số nhỏ đứng trước
    cout << s;
    return 0;
}

x = int(input())
if x == 0:                      # cần một chữ số 0, số dương nhỏ nhất là 10
    print(10)
elif x < 10:                    # bản thân x là một chữ số
    print(x)
else:
    s = ""
    for d in range(9, 1, -1):
        while x % d == 0:       # tách chữ số lớn trước
            s += str(d)
            x //= d
    if x != 1:                  # còn thừa số nguyên tố > 7
        print(-1)
    else:
        print(s[::-1])          # chữ số nhỏ đứng trước

C++▶ Chạy tay từng dòng codeTách chữ số từ 9 về 2, kiểm tra phần dư rồi đảo ngược xâu.

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

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 long long x;

6 cin >> x;

7 if (x == 0) { // cần một chữ số 0, số dương nhỏ nhất là 10

8 cout << 10;

9 return 0;

10 }

11 if (x < 10) { // bản thân x là một chữ số

12 cout << x;

13 return 0;

14 }

15 string s = "";

16 for (int d = 9; d >= 2; d--) {

17 while (x % d == 0) { // tách chữ số lớn trước

18 s += char('0' + d);

19 x /= d;

20 }

21 }

22 if (x != 1) { // còn thừa số nguyên tố > 7

23 cout << -1;

24 return 0;

25 }

26 reverse(s.begin(), s.end()); // chữ số nhỏ đứng trước

27 cout << s;

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: xâu s có không quá $\log_2 X \approx 30$ ký tự ⇒ $O(\log X)$.
• Thời gian: vòng for chỉ có 8 giá trị $d$; mỗi lần chia thành công thì $X$ giảm ít nhất một nửa nên tổng số lần chia không quá $\log_2 X \approx 30$ ⇒ $O(\log X)$, chạy tức thì nha các bạn.

Không gian$O(\log X)$

Thời gian$O(\log X)$

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với mọi $X$ từ 0 đến 3000 cùng 400 giá trị $X$ ngẫu nhiên tới $10^9$ (có cả số chứa thừa số 11, 13 và các trường hợp biên như $10^9$, $2^{29}$, $7^{10}$, số nguyên tố $999999937$), so với code vét cạn liệt kê mọi bộ chữ số có tích bằng $X$ – khớp hết; code vét cạn này lại được đối chiếu với việc duyệt thẳng $Y$ từ 1 đến $2 \cdot 10^6$. Riêng $X = 0$ mình hiểu theo đề là in 10 (số nguyên dương nhỏ nhất có tích chữ số bằng 0); đề không có ví dụ cho trường hợp này, bạn nào nộp thấy khác thì báo mình 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 😇