Editorial for New Year's '18 P2 - Mimi and Christmas Cake


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

Let F = \max(f_1, f_2, \dots, f_N).

For 10\% of points, we can iterate through each slice of cake, and then all integers from 2 to f_i-1, to check if any of them are a factor of f_i.

Time Complexity: \mathcal O(N F)

For an additional 10\% of points, we can process all the numbers from 2 to F, and record if they are prime or not in a boolean array, and then check if each f_i is prime or not.

Time Complexity: \mathcal O(N + F^2)

For the final 80\% of points, make the observation that if a_i is a factor of f_i and a_i \le \sqrt{f_i}, then \dfrac{f_i}{a_i} \ge \sqrt{f_i}. Namely, we only have to check for factors in the range [2, \sqrt{f_i}].

Alternatively, one could use a prime sieve, such as the sieve of Eratosthenes.

Time Complexity: \mathcal O(N + F \sqrt F) or \mathcal O(N \sqrt F), or \mathcal O(N + F \log \log F) with the sieve of Eratosthenes.


Comments

There are no comments at the moment.