Tìm số nguyên dương nhỏ nhất chia hết cho A và tổng chữ số bằng B trong Python

Cho hai số A và B, tìm số nguyên dương nhỏ nhất M sao cho M chia hết cho A và tổng các chữ số của M bằng B. Nếu không tồn tại, trả về -1.

Ví dụ: A = 50, B = 2, kết quả là 200 (chia hết cho 50, tổng chữ số 2+0+0=2).

Giải thuật (BFS trên trạng thái)

Sử dụng tìm kiếm theo chiều rộng (BFS) trên đồ thị trạng thái:

• Trạng thái: (remainder, sum_digits, string_số).
• Khởi tạo: (0, 0, "").
• Từ trạng thái hiện tại, thử thêm chữ số 0-9 vào cuối:
  • remainder mới = (remainder_cũ * 10 + chữ_số) % A.
  • sum_digits mới = sum_digits_cũ + chữ_số.
  • Chỉ xét nếu sum_digits mới ≤ B và trạng thái chưa được thăm.
• Khi tìm thấy trạng thái (0, B, string) → trả về int(string).
• Nếu hết hàng đợi mà không tìm thấy → trả về -1.

Ví dụ

visited = [[0 for _ in range(501)] for _ in range(5001)]

class Element:
    def __init__(self, a, b, string):
        self.a = a
        self.b = b
        self.string = string

def get_number(a, b):
    que = []
    elem = Element(0, 0, "")
    visited[0][0] = 1
    que.append(elem)
    while len(que) > 0:
        temp_elem = que.pop(0)
        if temp_elem.a == 0 and temp_elem.b == b:
            return int(temp_elem.string)
        for i in range(10):
            x = (temp_elem.a * 10 + i) % a
            y = temp_elem.b + i
            if y <= b and visited[x][y] == False:
                visited[x][y] = 1
                que.append(Element(x, y, temp_elem.string + str(i)))
    return -1

a, b = 50, 2
print(get_number(a, b))

Đầu vào

50, 2

Đầu ra

200