PROBLEM LINK:
Author: Denis Anishchenko
Tester: Hasan Jaddouh
Editorialist: Sarv Shakti Singh
Difficulty: Easy
Prerequisites: Basic maths, gcd
Problem: Given an array of length N and a number K, you are allowed to perform as many operations. In each operation, you can divide any element in the array with a positive number less than or equal to ‘K’. Determine if it possible to modify the array by applying as many operations in such a way that the GCD of the resulting array’s elements is 1.
Explanation: It is easy to see that the answer is NO if there exists a positive prime number greater than K that divides each element of the array. So, the answer is YES if the largest prime factor of the GCD of the array is less than or equal to K.
Once you have the GCD of the array, all that remains is to check if there exists a prime factor of the GCD that is greater than K. It could be done by this function:
bool check(int GCD, int K){
int max_prime = 1;
for(int i = 2; i <= sqrt(GCD); i++){ //find maximum of all the prime factors till sqrt
while(GCD % i == 0){
GCD /= i;
max_prime = max(max_prime, i);
}
}
max_prime = max(max_prime, GCD); //either GCD is reduced to 1 or a prime factor
//greater than sqrt(GCD)
if(max_prime <= K)
return true;
else
return false;
}
We have O(\sqrt{M} + n + \log{M}) solution per testcase, where M - is maximal number, O(\sqrt{M}) to factorize G and O(n + \log{M}) to calculate gcd of all numbers). It’s good exercise to think why counting of gcd of all numbers takes O(n + \log{M})).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.