Modified GCD

5

1 votes
Probabilities, Hard, Number Theory
Problem

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 MGCDK(A).

Here MGCDK(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 MGCDK(A).

CONSTRAINTS:

1N105

1K5

1Ai1012        

 

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In the above sample case 8 divides 5 elements of the array (24,8,48,56,16),Which is 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.

Editor Image

?