Editorial for DMOPC '15 Contest 1 P4 - Itami and Candy

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: cheesecake

We can precompute all primes up to $N$ ~N~ with Sieve of Eratosthenes. For each prime, we have two cases: Tuka takes either $0$ ~0~ or $1$ ~1~ candy. For each case, the number of ways we can give candies to Rory is the remaining number of candies $/X + 1$ ~/X + 1~ (integer division).

Time Complexity: $\mathcal{O}(N \log \log N)$ ~\mathcal{O}(N \log \log N)~

Comments

0

Plasmatic commented on June 27, 2019, 5:15 p.m. ← edit 3 →

sieve is $\mathcal{O}(N \log \log N)$ ~\mathcal{O}(N \log \log N)~

Edit: Apparently sieve can also have $\mathcal{O}(N)$ ~\mathcal{O}(N)~ complexity :O

Link: https://cp-algorithms.com/algebra/prime-sieve-linear.html