GEEK05 - Editorial

editorial
geek05
likecs
medium
queries
sieve

#1

Problem Link

Practice

Contest

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:

  1. (a + b) % m = ((a % m) + (b % m)) % m
  2. (a - b) % m = ((a % m) - (b % m) + m) % m
  3. (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* = \sum_{j=1}^{j=i} a*

To calculate a_i efficiently, we will use the general sieving technique. The pseudocode is given below :

for i in [1 : 100000]: a* = 2^i for i in [1 : 100000]: for j in [2*i, 3*i, ... 100000]: a[j] -= a*

To check why this code works, let us look at simple observations.

  1. 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.
  2. 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

  1. 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.
  2. 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}

Solution Links

Setter’s solution

Setter’s solution - 2


#2

Can you please provide the solution using mobius inversions?


#3

a_n = \sum_{d|n} {\mu(d) * {2}^{n/d}}. The second point in bonus part is wrong, as the complexity will be still O(n \log{n}), but the 3rd part is correct.