집합에 없는 최소 배수

면접 대비

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

요약

주어진 n개의 서로 다른 정수 집합에 없는 k의 가장 작은 양의 배수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

정수들의 집합 $A$ 가 주어진다. 집합 $A$ 에 속하지 않으면서 미리 정해진 수 $k$ 로 나누어떨어지는 가장 작은 양의 정수를 찾아야 한다.

다음을 수행하는 프로그램을 작성하라.

표준 입력에서 집합 $A$ 와 수 $k$ 를 읽는다.
집합 $A$ 에 속하지 않으면서 $k$ 로 나누어떨어지는 가장 작은 양의 정수를 구한다.
그 결과를 표준 출력에 출력한다.

입력

첫째 줄에 두 정수 $n$ 과 $k$ ( $1 ≤ n ≤ 10^6$ , $1 ≤ k ≤ 10^{12}$ )가 공백 하나로 구분되어 주어진다. $n$ 은 집합 $A$ 의 크기(원소의 개수)이다. 둘째 줄에 집합 $A$ 의 원소를 나타내는 $n$ 개의 정수 $a_i$ ( $1 ≤ a_i ≤ 10^{18}$ )가 공백 하나로 구분되어 주어진다. 모든 $a_i$ 는 서로 다르다.

출력

집합 $A$ 에 속하지 않으면서 $k$ 로 나누어떨어지는 가장 작은 양의 정수를 첫째 줄에 하나 출력한다.

예제3

예제 1
입력
```
6 2
3 8 1 2 4 10
```
예상 출력
```
6
```
예제 2
입력
```
3 1
1 2 3
```
예상 출력
```
4
```
예제 3
입력
```
3 5
1 2 3
```
예상 출력
```
5
```