PROBLEM LINK:
Author: Bhuvnesh Jain
Tester: Bhuvnesh Jain
Editorialist: Bhuvnesh Jain
DIFFICULTY:
HARD
PREREQUISITES:
Sqrt Trick, Prime counting function, Arithmetic Derivative
PROBLEM:
Evaluate the value of the function \sum_{x=1}^{x=N} F(N^k*x), for the function F(n) = strength(n) as given in problem statement.
EXPLANATION:
Let us evaluate F(n), the strength(n), for a number.
F(n) = \sum\limits_{p_i | n} \frac{n}{p_i}, where p_i need not be distinct.
F(ab) = a * F(b) + b * F(a), for a >= 1 , b >= 1
Let us see why the above claim is true. Consider the prime factors of n = a*b. Also consider the prime factors of a and b. The total number of prime factors of n is simply the union of the prime factors of a and b. So, iterate through first prime factors of a and then through b and you will get to know why above claim holds true.
F(N^k) = k * N^{k-1} * F(N).
To prove the above claim, use the above fact and derive a recurrence. For example,
F(N^2) = N * F(N) + N * F(N) = 2 * N * F(N)
F(N^3) = N * F(N^2) + N^2 * F(N) = 3 * N^2 * F(N) and so on.
Now, let us look at the problem given to us.
\sum_{x=1}^{x=N} F(N^k*x) = \sum_{x=1}^{x=n} x*F(N^k) + N^k*F(x)
=k*N^{k-1}*F(N) * \frac{N*(N+1)}{2} + N^k * \sum_{x=1}^{x=N} F(x)
The value of F(N) can be calculated in O(\sqrt{(N)}) complexity. We just need to efficiently find the value of the second summation.
\sum_{x=1}^{x=N} \sum_{p_i | x} \frac{x}{p_i}
To find a way to evaluate this function, let are change the summation such that we can evaluate the total sum, say P_i, that each prime p_i contributes to the final sum.
Now, let us evaluate see some pattern form for how the summation look like. Let us take N = 10.
p_i = 2, P_2 = (2/2 + 4/2 + 6/2 + 8/2 + 10/2) + (4/2 + 8/2) + (8/2)
p_i = 3, P_3 = (3/3 + 6/3 + 9/3) + (9/3)
p_i = 5, P_5 = (5/5 + 10/5)
p_i = 7, P_5 = (7/7)
Now, for every prime p_i that is less than \sqrt{n}, we can find the value of the sum in O(\log_{p} n) complexity. The number of primes below \sqrt{n} is approximately O(\frac{\sqrt{n}}{\log {\sqrt{n}}}). So, this step take an overall of O(\sqrt{n}) time. For primes below O(\sqrt{n}), you can just think of finding the summation as follows,
p_i = 2, P_2 = 1*(1+2+3+4+5) + 2*(1+2) + 4*(1)
i.e. \sum_{i=1} p^{i-1} * G(\frac{n}{p^i}), where G(n) = sum of first n positive integers.
Now for every prime, p_i greater than \sqrt{n}, we can group them by the final sum P_i they contribute to the answer. This trick is similar to the sqrt-trick used while calculating the sums of the form \frac{n}{i} where it can take only 2*\sqrt{n} values. But in this case, we need to find the number of primes in some given range like from \frac{n}{2} to \frac{n}{3}, \frac{n}{3} to \frac{n}{4} and so on. This is a known problem and can be solved in O(n^{3/4}) or O(n^{2/3}), for larger ranges and in O(1) after pre-computation using sieve. Doing this gives us a complexity of O(n^{3/4} * \sqrt{n}) but in practice it runs much faster in practice as the ranges in which we want to find number of primes decreasing very fast and after certain limit we can query in O(1) using the sieve we generated.
COMPLEXITY
O(\sqrt{n} + n^{3/4}*K), K is number of times prime counting function is called.