All Tracks Math Problem

Modified GCD
/

Number Theory, Probabilities

Problem
Editorial
Analytics

ASD and FGH are playing a game in which both take turns and asks each other to solve a Problem.Now it is ASD's turn.So ASD asked FGH to solve the following problem.He gave FGH an Array A containing positive integers A1,A2,A3,.....,AN and asked him to calculate \(MGCD_{\text{K}}(A)\).

Here \(MGCD_{\text{K}}(A)\) is the Modified GCD of Order K for Array A.

Modified GCD of Order K for an array is the Maximum number that divides at least  \(Ceil(N/K) \) number of elements of the array.For example Modified Gcd of Order 2 for array A is the Maximum number that divides at least half of its elements.

Here Ceil(x) means,x rounded up to the nearest positive integer.Ceil Function

FGH is unable solve this Problem and is asking for your help.Help him.

INPUT:​​​​

  • First line Contains two Positive Integers and K.
  • Second line contains N positive Integers A1,A2,A3.....AN,The Elements of Array A

OUTPUT:

Print a single line Containg a Positive Integer \(MGCD_{\text{K}}(A)\).

CONSTRAINTS:

\(1\le N \le 10^{5}\)

\(1\le K \le 5\)

\(1\le A_{i} \le 10^{12}\)        

 

SAMPLE INPUT
10 3
24 18 28 8 25 1 48 27 56 16
SAMPLE OUTPUT
8
Explanation

In the above sample case \(8\) divides \(5\) elements of the array \(( 24,8,48,56,16 )\),Which is \(\ge Ceil(8/3)=3\).There is no number greater than \(8\) that divides at least \(3\) numbers of the array.So \(8\) is the required answer.

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Уведомления
View All Notifications

?