在 Python 中查詢最小的正整數，使其可被 A 整除且其各位數字之和等於 B

假設我們有兩個數字 A 和 B，我們需要找到最小的正數 M，使得 M 可以被 A 整除，並且 M 的各位數字之和等於 B。如果不存在這樣的結果，則返回 -1。

例如，如果輸入為 A = 50，B = 2，則輸出將為 200，因為 200 可以被 50 整除，並且其各位數字之和為 2 + 0 + 0 = 2。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個包含兩個數字 a 和 b 以及一個字串的元素型別容器

• que := 一個新的列表

• elem := 一個新的元素，其值為 (0, 0, 空字串)

• visited[0, 0] := 1

• 將 elem 插入到 que 的末尾

• 當 que 的大小 > 0 時，執行以下操作：

  • temp_elem := 從 que 中刪除第一個元素

  • 如果 temp_elem.a 為 0 且 temp_elem.b 為 b，則

    • 返回 temp_elem.string 的整數形式

  • 對於 i 從 0 到 9，執行以下操作：

    • x := (temp_elem.a * 10 + i) mod a

    • y := temp_elem.b + i

    • 如果 y <= b 且 visited[x, y] 為 False，則

      • visited[x, y] := 1

      • 將一個新元素 (x, y, temp_elem.string 與 i 連線) 插入到 que 中

• 返回 -1

示例

讓我們來看以下實現，以便更好地理解：

線上演示

visited = [[0 for x in range(501)] for y 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(0, 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))

輸入

50, 2

輸出

200

Arnab Chakraborty

更新於: 2020年8月20日

209 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習