파이썬에서 A로 나누어지고 그 자릿수의 합이 B와 같도록 최소 양의 정수를 찾으십시오.

<시간/>

두 개의 숫자 A와 B가 있다고 가정하면 M이 A로 나누어지고 M의 자릿수의 합이 B와 같도록 최소 양수 M을 찾아야 합니다. 따라서 그러한 결과가 없으면 다음을 반환합니다. 1.

따라서 입력이 A =50, B =2인 경우 출력은 200이 됩니다. 이는 50으로 나누어지고 해당 숫자의 합 =2 + 0 + 0 =2이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

두 개의 숫자와 b와 하나의 문자열을 포함하는 하나의 요소 유형 컨테이너 정의
que :=새 목록
elem :=(0, 0, 빈 문자열)
이 있는 새 요소
방문[0, 0] :=1
que의 끝에 요소 삽입
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) 모드 a
  - y :=temp_elem.b + i
  - y <=b이고 방문된[x, y]가 False이면
    - 방문[x, y] :=1
    - x, y 및 temp_elem.string이 있는 새 요소를 삽입하여 i를 연결합니다.
반환 -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