GCD

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

요약

최대 1e5개의 정수가 담긴 배열에서 최대 k개의 원소를 지워, 남은 원소들의 최대공약수를 가장 크게 만드는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 확률
정답자: 아직 제출이 없습니다

문제

정수 배열 $a_1, a_2, \ldots, a_n$ 이 주어진다. 원소를 최대 $k$ 개까지 지울 수 있을 때, 배열에 남은 모든 원소의 최대공약수가 가질 수 있는 최댓값을 구하라 ( $k \le \frac{n}{2}$ ).

입력

첫 줄에는 배열의 원소 개수 $n$ 과 지울 수 있는 원소의 최대 개수 $k$ 가 주어진다 ( $2 \le n \le 10^5$ , $0 \le k \le \frac{n}{2}$ ). 둘째 줄에는 배열 $a$ 의 원소 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^{18}$ ).

출력

원소를 최대 $k$ 개까지 지운 뒤, 남은 모든 원소의 최대공약수가 가질 수 있는 최댓값을 출력한다.

예제3

예제 1
입력
```
4 1
6 15 35 14
```
예상 출력
```
1
```
예제 2
입력
```
4 2
6 15 35 14
```
예상 출력
```
7
```
예제 3
입력
```
3 1
897612484786617600 5828 16027
```
예상 출력
```
1457
```