아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

나눗셈

시간 제한2초메모리 제한512 MB

요약
n의 자릿수를 최소한만 바꿔 앞에 0이 없으면서 m으로 나누어떨어지는 수를 만들고, 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
동적 계획법, 수학, 그리디, 완전 탐색
정답자
아직 제출이 없습니다

문제

오늘 레샤는 학교에서 세로 나눗셈을 배웠다. 숙제로 두 큰 수 nn과 mm의 몫을 계산해야 한다. 레샤는 이미 문제를 풀어 보았지만, 뜻밖에도 nn이 mm으로 나누어떨어지지 않는다는 것을 깨달았다. 그는 선생님이 나머지가 없는 예제를 냈다고 확신하기 때문에, 칠판에서 문제를 옮겨 적을 때 실수했다고 생각했다.

이제 그는 nn의 몇 자리를 고쳐서 mm으로 나누어떨어지게 만들고 싶다. 이때 레샤는 새 수가 자신이 적은 수와 최소한의 위치에서만 달라지기를 원한다.

레샤가 적은 수에는 앞에 오는 0이 없으며, 칠판에 적힌 수도 앞에 오는 0이 없었다고 확신하기 때문에 새 수에도 앞에 오는 0이 없어야 한다. 수 0 자체는 허용된다.

레샤를 도와주자.

입력

입력 파일의 유일한 줄에 두 정수 nn, mm이 주어진다 (0≤n≤10110 \le n \le 10^{11}, 1≤m≤10111 \le m \le 10^{11}).

출력

출력 파일의 유일한 줄에 하나의 정수를 출력한다. 이는 nn의 최소 자릿수를 바꾸어 얻은 수가 앞에 오는 0이 없고 mm으로 나누어떨어지게 하는 결과이다.

답이 여러 개면 아무거나 출력해도 된다. 답이 존재하지 않으면 −1-1을 출력한다.

예제4

  1. 예제 1

    입력
    123 10
    
    예상 출력
    120
    
  2. 예제 2

    입력
    123 141
    
    예상 출력
    423
    
  3. 예제 3

    입력
    9 123
    
    예상 출력
    0
    
  4. 예제 4

    입력
    12 123
    
    예상 출력
    -1