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

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)$ $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)$ $O (N \log \log N)$

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

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