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)$ $O (A_{i})$ time, and then check if they are prime in $\mathcal O(A_i)$ $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)$ $O (N)$ time.

Time Complexity: $\mathcal O(N \max(A_i)^2)$ $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))$ $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))$ $O (N + \log max (A_{i}))$ . The proof is an exercise.

We can then prime factorize the GCD in $\mathcal O(\sqrt G)$ $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)})$ $O (N + \sqrt{max (A_{i})})$

Comments

There are no comments at the moment.