def find_largest_A(N, M):
# Chuyển số N thành danh sách các chữ số và sắp xếp giảm dần
digits = sorted(list(str(N)), reverse=True)

# Trường hợp chia hết cho 10: Số cuối cùng phải là 0
if M == 10:
if '0' in digits:
digits.remove('0')
return "".join(digits) + '0'
return -1

# Trường hợp chia hết cho 2: Số cuối cùng phải chẵn (0, 2, 4, 6, 8)
if M == 2:
# Tìm chữ số chẵn nhỏ nhất để đặt ở hàng đơn vị
even_digits = [d for d in digits if int(d) % 2 == 0]
if not even_digits:
return -1
last_digit = min(even_digits)
digits.remove(last_digit)
return "".join(digits) + last_digit

# Trường hợp chia hết cho 4: 2 chữ số cuối tạo thành số chia hết cho 4
if M == 4:
best_A = ""
# Thử mọi cặp chữ số làm hàng chục (j) và hàng đơn vị (i)
for i in range(len(digits)):
for j in range(len(digits)):
if i == j: continue
if int(digits[j] + digits[i]) % 4 == 0:
temp = digits[:]
d_i, d_j = digits[i], digits[j]
temp.remove(d_i)
temp.remove(d_j)
current_A = "".join(temp) + d_j + d_i
if current_A > best_A:
best_A = current_A
return best_A if best_A else -1

# Trường hợp chia hết cho 6: Tổng chữ số chia hết cho 3 và số cuối chẵn
if M == 6:
total_sum = sum(int(d) for d in digits)
if total_sum % 3 != 0: return -1 # Nếu tổng không chia hết cho 3 thì không thể tạo số chia hết cho 6

even_digits = [d for d in digits if int(d) % 2 == 0]
if not even_digits: return -1
last_digit = min(even_digits)
digits.remove(last_digit)
return "".join(digits) + last_digit

# Trường hợp chia hết cho 8: 3 chữ số cuối tạo thành số chia hết cho 8
if M == 8:
best_A = ""
for i in range(len(digits)): # đơn vị
for j in range(len(digits)): # chục
for k in range(len(digits)): # trăm
if i == j or j == k or i == k: continue
if int(digits[k] + digits[j] + digits[i]) % 8 == 0:
temp = digits[:]
d_i, d_j, d_k = digits[i], digits[j], digits[k]
temp.remove(d_i); temp.remove(d_j); temp.remove(d_k)
current_A = "".join(temp) + d_k + d_j + d_i
if current_A > best_A:
best_A = current_A
return best_A if best_A else -1

# Ví dụ sử dụng:
N = 12345
M = 4
print(f"Số lớn nhất từ {N} chia hết cho {M} là: {find_largest_A(N, M)}")

def find_largest_A(N, M):
# Chuyển số N thành danh sách các chữ số và sắp xếp giảm dần
digits = sorted(list(str(N)), reverse=True)

# Trường hợp chia hết cho 10: Số cuối cùng phải là 0
if M == 10:
if '0' in digits:
digits.remove('0')
return "".join(digits) + '0'
return -1

# Trường hợp chia hết cho 2: Số cuối cùng phải chẵn (0, 2, 4, 6, 8)
if M == 2:
# Tìm chữ số chẵn nhỏ nhất để đặt ở hàng đơn vị
even_digits = [d for d in digits if int(d) % 2 == 0]
if not even_digits:
return -1
last_digit = min(even_digits)
digits.remove(last_digit)
return "".join(digits) + last_digit

# Trường hợp chia hết cho 4: 2 chữ số cuối tạo thành số chia hết cho 4
if M == 4:
best_A = ""
# Thử mọi cặp chữ số làm hàng chục (j) và hàng đơn vị (i)
for i in range(len(digits)):
for j in range(len(digits)):
if i == j: continue
if int(digits[j] + digits[i]) % 4 == 0:
temp = digits[:]
d_i, d_j = digits[i], digits[j]
temp.remove(d_i)
temp.remove(d_j)
current_A = "".join(temp) + d_j + d_i
if current_A > best_A:
best_A = current_A
return best_A if best_A else -1

# Trường hợp chia hết cho 6: Tổng chữ số chia hết cho 3 và số cuối chẵn
if M == 6:
total_sum = sum(int(d) for d in digits)
if total_sum % 3 != 0: return -1 # Nếu tổng không chia hết cho 3 thì không thể tạo số chia hết cho 6

even_digits = [d for d in digits if int(d) % 2 == 0]
if not even_digits: return -1
last_digit = min(even_digits)
digits.remove(last_digit)
return "".join(digits) + last_digit

# Trường hợp chia hết cho 8: 3 chữ số cuối tạo thành số chia hết cho 8
if M == 8:
best_A = ""
for i in range(len(digits)): # đơn vị
for j in range(len(digits)): # chục
for k in range(len(digits)): # trăm
if i == j or j == k or i == k: continue
if int(digits[k] + digits[j] + digits[i]) % 8 == 0:
temp = digits[:]
d_i, d_j, d_k = digits[i], digits[j], digits[k]
temp.remove(d_i); temp.remove(d_j); temp.remove(d_k)
current_A = "".join(temp) + d_k + d_j + d_i
if current_A > best_A:
best_A = current_A
return best_A if best_A else -1

# Ví dụ sử dụng:
N = 12345
M = 4
print(f"Số lớn nhất từ {N} chia hết cho {M} là: {find_largest_A(N, M)}")