Editorial for Sharing Chocolate

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

Editorialist: Tommoa

This is the first question from the second PCS standard contest.

In this problem, we are effectively trying to get the number of factors of a given number $N$ . There are three sub-problems of increasing difficulty based on the input size that we will cover seperately.

20 points: $1 \leq Q, N \leq 5000$

The naive approach to generating all of the factors for $N$ is to test every number $i$ up to $N$ and if $N$ then we can add one to the number the factors for $N$ . This has a time complexity of $O (N \times Q)$ , which given an approximation of $10^{8}$ operations per second and the worst bounds for this sub-problem, works out to around $0.25$ seconds, more than enough to fit in the time limit.

20 points: $1 \leq Q, N \leq 100000$

Now we need to be a bit more efficient. If we try the previous method, we'll end up taking around $100$ seconds in the worst case scenario.

Each number only has factors up to $\sqrt{N}$ that have a unique pair. We can use this property to only go up to $\sqrt{N}$ instead of $N$ for every $Q$ , adding $2$ to the number of factors for every number we find that matches so long as it is $\neq \sqrt{N}$ . This observation puts our time complexity at $O (\sqrt{N} \times Q)$ , leaving us with about $0.32$ seconds for the worst possible test case.

60 points: $1 \leq Q, N \leq 1000000$

Once again, our old optimisations time out, this time at around $10$ seconds. But alas, we have no optimisations left!

Fear not though, Eratosthenes is here to save the day! The sieve of Eratosthenes, is a method for finding primes which is still one of the most efficient algorithms to date (despite being a few thousand years old). The sieve works by taking an array of numbers all marked as being primes, taking the smallest of them and multiplying it through the table, and repeating until the table is full. While there is a way to figure out the number of factors of a number using prime factors, we're going to use a modified sieve instead to declare the number of factors a given number has instead.

If we go through each number before reading any input, we can pre-compute the number of primes any given number has using a modified sieve of Eratosthenes, and then easily read our input and instantly output the correct value, putting our time complexity at $O (N \log (N)) + Q)$ and fitting us well below the target time.

Copy

#include <bits/stdc++.h>
using namespace std;

int main() {
    int Q, N;
    cin >> Q;
    vector<int> sieve(1000001, 1);
    for (int i = 2; i < sieve.size(); ++i) {
        for (int j = i; j < sieve.size(); j += i) {
            ++sieve[j];
        }
    }
    for (Q--) {
        cin >> N;
        cout << sieve[N] << endl;
    }
}

Comments

0
emma commented on Nov. 30, 2018, 3:26 p.m.
clever! After reading the editorial, I've changed my program according to your solution yet I still get TLE error using c++, why would that be?

the generating part

" ...

Copy
n=1000001; for (i=2; i<=n; i++) { for (j=i; j<=n; j+=i) tot[j]++; }

.. "

0

maxward commented on Dec. 1, 2018, 12:43 a.m.

The reason your solution is getting TLE is because it uses slow I/O methods. Read the discussion here: https://pcs.ucc.asn.au/problem/aplusb

0

emma commented on Dec. 1, 2018, 7:09 a.m.

Thank you, it worked!