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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let .
For of points, we can iterate through each slice of cake, and then all integers from to , to check if any of them are a factor of .
Time Complexity:
For an additional of points, we can process all the numbers from to , and record if they are prime or not in a boolean array, and then check if each is prime or not.
Time Complexity:
For the final of points, make the observation that if is a factor of and , then . Namely, we only have to check for factors in the range .
Alternatively, one could use a prime sieve, such as the sieve of Eratosthenes.
Time Complexity: or , or with the sieve of Eratosthenes.
Comments