Ước Chung Dễ Dàng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Pypy 3 3.0s
Python 3 3.0s
Tác giả:
ami
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami không thích ước chung lớn nhất. Do đó, ami sẽ cần các bạn tìm ước chung lớn nhất giúp ami. Cho một dãy \(n\) số nguyên dương. Hãy tính ước chung lớn nhất của \(n\) số này.

"Dễ quá" - các bạn thầm nghĩ. Vậy nên ami muốn các bạn bỏ đi đúng 1 số để ước chung lớn nhất của các số còn lại là lớn nhất.

"Vẫn quá dễ" - các bạn cười thầm. Vì thế, hãy bỏ đi \(k\) số để ước chung lớn nhất của các số còn lại là lớn nhất nhé.

Input

  • Dòng đầu chứa 2 số nguyên \(n\) và \(k\).

  • Dòng tiếp theo chứa n số nguyên dương \(a_1\), \(a_2\), ..., \(a_n \ (1 \leq a_i \leq 3 \times 10^6)\).

Output

  • In ra \(1\) dòng là ước chung lớn nhất của dãy số sau khi đã bỏ đi đúng k số.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), và \(k = 0\).

  • Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 10^5\), và \(k = 1\).

  • Subtask \(3\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 10^5\).

  • Subtask \(4\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 3*10^6\).

Example

Test 1

Input 
3 1
1 2 2
Output 
2
Note

Sau khi bỏ đi số 1, các bạn còn [2 2]. Gcd(2 , 2) = 2.

Bình luận