PythonでAで割り切れ、その桁の合計がBに等しくなるような最小の正の整数を見つけます

2つの数AとBがあるとすると、MがA​​で割り切れ、Mの桁の合計がBと同じになるように、最小の正の数Mを見つける必要があります。したがって、そのような結果がない場合は、-を返します。 1.

したがって、入力がA =50、B =2の場合、出力は200になります。これは、50で割り切れ、その桁の合計=2 + 0 + 0=2です。

これを解決するには、次の手順に従います-

• 2つの数値aとbと1つの文字列を含む1つの要素タイプのコンテナを定義します

• que：=新しいリスト

• elem：=（0、0、空白の文字列）を含む新しい要素

• 訪問済み[0,0]：=1

• queの最後にelemを挿入します

• queのサイズが0より大きい場合、実行します

  • temp_elem：=queから最初の要素を削除

  • temp_elem.aが0で、temp_elem.bがbの場合、

    • temp_elem.stringの整数を返します

  • 0から9の範囲のiの場合、実行

    • x：=（temp_elem.a * 10 + i）mod a

    • y：=temp_elem.b + i

    • y <=bでvisited[x、y]がFalseの場合、

      • 訪問済み[x、y]：=1

      • x、y、temp_elem.stringを使用して新しい要素を挿入します。iをintoqueに連結します

• -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