在 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习