×

# GEEK05 - Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

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[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 [2i, 3i, ... 100000]: a[j] -= a[i] 

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 asked 20 Nov '17, 22:01 6★likecs 3.7k2380 accept rate: 9% 0★admin ♦♦ 19.7k350498541 One Answer:  0 Can you please provide the solution using mobius inversions? answered 20 Nov '17, 23:31 2.8k●1●4●18 accept rate: 16%$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. (21 Nov '17, 00:56) likecs6★  toggle preview community wiki: Preview ### Follow this question By Email: Once you sign in you will be able to subscribe for any updates here By RSS: Answers Answers and Comments Markdown Basics • *italic* or _italic_ • **bold** or __bold__ • link:[text](http://url.com/ "title") • image?![alt text](/path/img.jpg "title") • numbered list: 1. Foo 2. Bar • to add a line break simply add two spaces to where you would like the new line to be. • basic HTML tags are also supported • mathemetical formulas in Latex between$ symbol

Question tags:

×15,497
×2,559
×593
×301
×65
×6

question asked: 20 Nov '17, 22:01

question was seen: 413 times

last updated: 26 Nov '17, 16:34