Problem Link
Author: Bhuvnesh Jain
Tester: Bhuvnesh Jain
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM
Prerequisites
Sieving Techniques, Modular Arithmetic, Prefix Sums.
Problem
Find the sum of {a}_{l} \dots {a}_{r}, where array a satisfy the follwoing property,
\sum_{d | n} {a}_{d} = {2}^{n}
Explanation
First of all, we see some basic properties of modular arithmetic:
- (a + b) % m = ((a % m) + (b % m)) % m
- (a - b) % m = ((a % m) - (b % m) + m) % m
- (a * b) % m = ((a % m) * (b % m)) % m
For the 3rd property, care must be taken while doing the multiplication, as the value may be an integer, while there may be overflow in the intermediate multiplication operation.
Now, assume we have all the values of a_i calculted in efficient way, then we can answer the sums in every query naively in O(r-l). To do this efficiently, we can simply precompute the prefix sums and then answer the query in O(1), as :
ANS = prefix[r] - prefix[l-1], where prefix[i] = \sum_{j=1}^{j=i} a[i]
To calculate a_i efficiently, we will use the general sieving technique. The pseudocode is given below :
for i in [1 : 100000]:
a[i] = 2^i
for i in [1 : 100000]:
for j in [2*i, 3*i, ... 100000]:
a[j] -= a[i]
To check why this code works, let us look at simple observations.
- We know initial terms are as a[1] = 2, a[1] + a[2] = 4, a[1] + a[3] = 8, a[1] + a[2] + a[4] = 16, a[1] + a[5] = 32 and so on.
- Thus, once we have calculated the correct answer for particular $i$, we will subtract its contribution from other $a_j$, to which it contributes to their sum. For example, we know $a[1]$ initially, so, we subtract it from $2, 3, \dots$. Thus, we get the correct values of a[2], a[3], a[5] etc. Now, we subtract $a[2]$ from $4, 6, 8 \dots$, and we get the correct value of 4. Thus the process continues.
The time complexity of this approach is O(n/1 + n/2 + n/3 + n/4 + \dots + n/n) = O(n \log{n}).
Bonus Problems
- As the constraints are not that large, we can even do a naive brute force to calculate the values, in $O(N * sqrt(N)). See setter's solution 2 below.
- As constraints allowed storing the pre-computed values in an array, the above approaches were good enough. What is the number of queries were reduced, but $L, R$ were up to now ${10}^{11}$. We can still use the idea of mobius inversions and some other transforms to give the answer to each query in $O({n}^{3/4})$. Try to think about this one? You can also refer to [this video](https://www.youtube.com/watch?v=_noJI8UkTq8&t=31s) by kevinsogo for some help.
Time Complexity
O(N * \log{N} + Q), where N = Max value of R i.e {10}^{5}
Space Complexity
O(N), where N = {10}^{5}