All Tracks Math Problem

Modified GCD
Tag(s):

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

National Institute of Technology, Silchar

Challenge Name

NITS Short-Circuit #1

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?