PROBLEM LINK: Problem
Author and editorialist: Denis Anishchenko
Tester: Hasan Jaddouh
DIFFICULTY: Simple
PREREQUISITES: Basic maths
EXPLANATION:
Let’s consider gcd of all numbers in array (let’s denote G). G = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} where k - is number of distinct prime dividers of G. It’s easy to see that the answer is ‘YES’ when all p_i \leq k, because we can divide all numbers in array A while they are divisible by some p_i. Otherwise the answer is ‘NO’ because all numbers in array are divisible by some p_i > k and we can’t ‘kill’ this prime. So, we have O(\sqrt{MX} + n + \log{MX}) solution per testcase, where MX - is maximal number, (O(\sqrt{MX}) to factorize G and O(n + \log{MX}) to calculate gcd of all numbers). It’s good exercise to think why counting of gcd of all numbers takes O(n + \log{MX})).