LARGEDIV - Editorial

PROBLEM LINK:

Practice

Author: Manas Rawat
Tester: Aagam Jain
Editorialist: Manas Rawat

DIFFICULTY:

EASY

PREREQUISITES:

number-theory, GCD

PROBLEM:

Given an array of N integers you have the find the Kth largest number that divides all the integers present in the array.

EXPLANATION:

The most important observation here is that the GCD of the integers present in the array will be the largest number that divides all the integers in the array. Now if we find the divisors of the GCD obtained they will also be the divisors if the integers present in the array.

So we just need to find all the factors of the GCD of all the integers present in the array and just print the Kth largest of them.

SOLUTIONS:

Solution can be found here.