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) time, and then check if they are prime in \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) time.

Time Complexity: \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)), by using the Euclidean algorithm. We can then prime factorize the GCD in \mathcal O(\sqrt G) time, where G is the GCD, and return the largest prime factor.

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


Comments

There are no comments at the moment.