Editorial for DMOPC '17 Contest 5 P3 - Mimi and Primes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For the first subtask, it is possible to iterate through all factors of a number in $\mathcal O(A_i)$ ~\mathcal O(A_i)~ time, and then check if they are prime in $\mathcal O(A_i)$ ~\mathcal O(A_i)~ time. If said factor is prime, we can iterate through the array and see if every number in the array is a multiple in $\mathcal O(N)$ ~\mathcal O(N)~ time.

Time Complexity: $\mathcal O(N \max(A_i)^2)$ ~\mathcal O(N \max(A_i)^2)~

Bonus: The time complexity given above is a very loose upper bound. Can you establish a tighter bound?

For the second subtask, we can find the GCD of the array in $\mathcal O(N \log \max(A_i))$ ~\mathcal O(N \log \max(A_i))~ by using the Euclidean algorithm. Bonus: This bound can be improved to $\mathcal O(N + \log \max(A_i))$ ~\mathcal O(N + \log \max(A_i))~. The proof is an exercise.

We can then prime factorize the GCD in $\mathcal O(\sqrt G)$ ~\mathcal O(\sqrt G)~ time, where $G$ ~G~ is the GCD, and return the largest prime factor.

Time Complexity: $\mathcal O(N + \sqrt{\max(A_i)})$ ~\mathcal O(N + \sqrt{\max(A_i)})~

Comments

There are no comments at the moment.