### PROBLEM LINK:

**Author:** Constantine Sokol

**Tester:** Pavel Sheftelevich

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

simple

### PREREQUISITES:

finding sum of divisors of a number

### PROBLEM:

Let’s define f_n as the sum of all odd divisors of n. You are given at max 10 queries of following types to answer

- Given two (l, r), output value of f_l + f_{l + 1} + \dots+ f_{r - 1} + f_r. Range of l, r will be [1, 10^5].

### QUICK EXPLANATION:

- Precompute f_n for all n from 1 to 10^5 using sieve in \mathcal{O}(n \, log n) time. Now, for answering each query, you can answer in \mathcal{O}(r - l + 1).
- Let n = 2^r * s such that s is odd. Let prime representation of s be p_1^{q_1} * p_2^{q_2} * \dots * p_r^{q_r}. Then value of f_n will be

### EXPLANATION:

Let M = 10^5.

### Sieve based solution

The problem is very similar to finding sum of all the divisors of a number, only change is that we should only consider odd divisors.

We will use a sieve to precompute sum of all divisors for number \leq M. So, we iterate over each odd i from 1 to M, then we iterate over each multiple d of i, s.t. d \leq M and add i to f_d as i is an odd divisor of d. See the following pseudo code for details.

```
for (int i = 1; i <= M; i += 2) {
for (int d = i; d <= M; d += i) {
f[d] += i
}
}
```

Now, you might be thinking that its time complexity is \mathcal{O}(M^2). Not it’s not, in fact it is only \mathcal{O}(M \, log M).

**Proof**

For each i, we iterate over all its multiples d such that d \leq M. Number of such d's can be at max \frac{M}{i}.

So, our time complexity will be

### Prime representation of number based solution

Let us first remove all the factors of 2 from n, i.e. n = 2^r * s such that s is odd.

Now, say prime representation of s be p_1^{q_1} * p_2^{q_2} * \dots * p_r^{q_r}, then value of f_n will be

**Proof**

Consider the following product

\begin{equation}

(1 + p_1 + p_1^2 + \dots + p_1^{q_1}) \cdot (1 + p_2 + p_2^2 + \dots + p_2^{q_2}) \cdot \dots * (1 + p_r + p_r^2 + \dots + p_r^{q_r})

\end{equation}

Notice that upon expending this product, its each term will be a product of some powers of p_1, p_2, \dots p_r, i.e. each term will be a divisor of s.

Also, notice that each of the term in the expression will be unique, i.e. each divisor is added only once. Hence this expression represents sum of all divisors of s.

As we know the formula for sum of a geometric progression

Thus follows the proof.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.