Tóm tắt đề bài

Cho hai số tự nhiên \(N\) và \(M\) (trong đó \(M\) là số chẵn, \(2 \le M \le 10\)). Ta được phép sắp xếp lại các chữ số của \(N\) (mỗi chữ số dùng không vượt quá số lần xuất hiện trong \(N\)) để tạo thành một số \(A\). Hãy tìm giá trị lớn nhất của \(A\) sao cho \(A\) chia hết cho \(M\). Nếu không tạo được thì in ra \(0\).

Phân tích

• \(N \le 10^{15}\) nên số chữ số của \(N\) tối đa là \(15\).
• \(M\) chỉ thuộc tập \(\{2,4,6,8,10\}\) nên có thể khai thác các dấu hiệu chia hết:
  • Chia hết cho \(2\): chữ số cuối chẵn.
  • Chia hết cho \(4\): 2 chữ số cuối chia hết cho \(4\).
  • Chia hết cho \(8\): 3 chữ số cuối chia hết cho \(8\).
  • Chia hết cho \(10\): chữ số cuối là \(0\).
  • Chia hết cho \(6\): vừa chia hết cho \(2\) vừa chia hết cho \(3\) (tổng chữ số chia hết cho \(3\)).

Nhận xét quan trọng:

• Để số tạo ra là lớn nhất, ta muốn các chữ số ở đầu càng lớn càng tốt.
• Với các tiêu chuẩn chia hết theo “đuôi” (2/4/8/10), ta có thể:
  • Chọn một “đuôi” hợp lệ (1–3 chữ số tùy \(M\)),
  • Các chữ số còn lại sắp giảm dần và đặt lên trước,
  • Từ đó tạo ra ứng viên rất lớn.

AC code cung cấp hiện thực ý tưởng này bằng cách:

• Sắp chữ số \(N\) giảm dần ngay từ đầu.
• Sinh các “đuôi” có thể (với \(M \in \{2,4,8\}\) và \(6\) là trường hợp đặc biệt).
• Ghép lại thành các ứng viên rồi lấy lớn nhất chia hết cho \(M\).

Hướng giải quyết

Nhận xét

• Với \(M = 2,4,8\): điều kiện chia hết chỉ phụ thuộc vào \(k\) chữ số cuối (\(k=1,2,3\)). Ta thử tất cả các giá trị đuôi có thể trong phạm vi nhỏ:
  • \(M=2\): thử \(xx \in [0,9]\) sao cho \(xx \equiv 0 \pmod 2\) (tối đa 5 giá trị).
  • \(M=4\): thử \(xx \in [0,99]\) sao cho \(xx \equiv 0 \pmod 4\) (tối đa 25 giá trị).
  • \(M=8\): thử \(xx \in [0,999]\) sao cho \(xx \equiv 0 \pmod 8\) (tối đa 125 giá trị).

• Với mỗi \(xx\):

  • Kiểm tra có thể “lấy” các chữ số của str(xx) từ multiset chữ số của \(N\) không.
    • Lưu ý: str(xx) không có các số 0 ở đầu, ví dụ \(xx=8\) tương ứng đuôi "8" chứ không phải "008"; AC code làm đúng theo kiểu này.
  • Nếu lấy được, phần chữ số còn lại để nguyên thứ tự giảm dần, rồi append str(xx) ở cuối để tạo ứng viên.

• Với \(M = 6\):

  • Cần chia hết cho \(2\) và \(3\).
  • Tổng chữ số của mọi hoán vị là như nhau, nên nếu \(\sum\) chữ số của \(N\) không chia hết cho \(3\) thì không thể có số nào chia hết cho \(6\).
  • Nếu chia hết cho \(3\), bài toán quy về đảm bảo chia hết cho \(2\) (chọn đuôi chẵn như trường hợp \(M=2\)).

• Với \(M = 10\):

  • Cần chữ số cuối là \(0\). Nếu \(N\) có ít nhất một chữ số 0, số lớn nhất đạt được là sắp giảm dần toàn bộ chữ số (vì đã có 0 nằm cuối sau khi sort giảm dần).

Cuối cùng, AC code còn kiểm tra lại int(x) % m == 0 cho mọi ứng viên (để an toàn) và lấy max.

Thuật toán (theo đúng AC code)

1. Đọc \(N\) dưới dạng chuỗi, chuyển thành danh sách chữ số n, sắp xếp giảm dần.
2. Tạo danh sách Ans chứa các ứng viên dạng chuỗi.
3. Hàm Chia_m(n, x, m):
   • Duyệt xx từ \(0\) đến \(x-1\) bước \(m\) (tức là mọi bội của \(m\) trong đoạn).
   • Với mỗi xx:
     • Tạo bản sao tmp = n.copy().
     • Với từng ký tự i trong str(xx), nếu i có trong tmp thì xóa một lần (remove).
     • Nếu xóa đủ toàn bộ chữ số của str(xx):
       • tmp.append(str(xx)) (ghép cả chuỗi đuôi thành 1 phần tử cuối),
       • Đưa ''.join(tmp) vào Ans.
4. Xét theo từng \(M\):
   • Nếu \(M=2\): gọi Chia_m(n, 10, 2).
   • Nếu \(M=4\): gọi Chia_m(n, 100, 4).
   • Nếu \(M=6\):
     • Tính tổng chữ số \(S\); nếu \(S \bmod 3 = 0\) thì gọi Chia_m(n, 10, 2).
   • Nếu \(M=8\): gọi Chia_m(n, 1000, 8).
   • Nếu \(M=10\): nếu chữ số nhỏ nhất (sau sort giảm dần thì ở cuối) là '0' thì thêm luôn ''.join(n) vào Ans.
5. Duyệt các chuỗi x trong Ans, nếu int(x) % M == 0 thì cập nhật Max.
6. In Max (mặc định \(0\) nếu không có).

Lưu ý / Pitfall

• Khi kiểm tra chữ số của xx, việc dùng str(xx) khiến các đuôi như 008 không được xét dưới dạng 3 chữ số. Tuy nhiên AC code vẫn đúng theo cách hiểu “chọn một số tạo bởi các chữ số” (không có số 0 ở đầu của toàn bộ số). Việc thiếu “0 ở đầu của đuôi” không làm mất nghiệm lớn nhất trong bối cảnh sắp chữ số giảm dần ở phía trước và đuôi chỉ đóng vai trò điều kiện chia hết.
• Dùng tmp.remove(i) là \(O(\text{len}(N))\), nhưng vì số chữ số \(\le 15\) và số xx thử tối đa \(125\), vẫn rất nhỏ.

Độ phức tạp

• Gọi \(d\) là số chữ số của \(N\) (\(d \le 15\)).
• Với \(M=8\) là lớn nhất: thử khoảng \(125\) giá trị xx, mỗi giá trị xử lý tối đa 3 ký tự và remove trên mảng dài \(\le 15\).

Do đó:

• Thời gian: \(O(125 \cdot d^2)\) (rất nhỏ, thực tế gần như hằng số).
• Bộ nhớ: \(O(|Ans| \cdot d)\), với \(|Ans| \le 125\).

Code tham khảo

def Chia_m(n, x, m):
    # Sinh các ứng viên bằng cách chọn một "đuôi" xx (bội của m)
    # sao cho các chữ số của str(xx) lấy được từ n.
    for xx in range(0, x, m):  # xx = 0, m, 2m, ...
        tmp = n.copy()
        cnt = 0
        for i in str(xx):
            if i in tmp:
                tmp.remove(i)      # xóa 1 lần xuất hiện của chữ số i
                cnt += 1
        if cnt == len(str(xx)):     # lấy được đủ chữ số để tạo đuôi
            tmp.append(str(xx))     # ghép đuôi vào cuối
            Ans.append(''.join(tmp))

n = list(input().strip())
m = int(input().strip())

n.sort(reverse=True)
Ans = []
Max = 0

if m == 2:
    Chia_m(n, 10, 2)
elif m == 4:
    Chia_m(n, 100, 4)
elif m == 6:
    S = sum(list(map(int, n)))
    if S % 3 == 0:
        Chia_m(n, 10, 2)            # cần thêm điều kiện chia hết cho 2
elif m == 8:
    Chia_m(n, 1000, 8)
else:  # m == 10
    if n[-1] == '0':
        Ans.append(''.join(n))

for x in Ans:
    if int(x) % m == 0:
        Max = max(Max, int(x))

print(Max)