Editorial for Sharing Chocolate
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
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}\leq5000\)
The naive approach to generating all of the factors for \(N\) is to test every number \(i\) up to \(N\) and if \(N%i=0\) 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.
#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
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
" ...
.. "
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
Thank you, it worked!