Ước Chung Dễ Dàng

View as PDF




Time limit:
Pypy 3 3.0s
Python 3 3.0s

Author:
Problem type
Points: 300 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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\)\(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.


Comments (4)

Order by
Loading comments...