ODDDIV - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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
\frac{(p_1^{q_1 + 1} - 1)}{p_1 - 1} \cdot \frac{(p_2^{q_2 + 1} - 1)}{p_2 - 1} \cdot \dots \cdot \frac{(p_r^{q_r + 1} - 1)}{p_r - 1}

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

\begin{aligned} \textbf{Time Complexity} & = \frac{M}{1} + \frac{M}{2} + \dots + \frac{M}{M} \\ &= M * (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{M}) \\ & \leq M * (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{M} + \dots + \text{ infinite terms}) \\ & \leq M * log M \\ & \text{ as } (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{M} + ..) \text{ is harmonic series whose sum is bounded by log(number of terms)}. \end{aligned}

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

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

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

\begin{aligned} 1 + p_1 + p_1^2 + .. p_1^{q_1} & = \frac{(p_1^{q_1 + 1} - 1)}{p_1 - 1} \\ i.e., \sum_{i = 1}^{q_1} {p_1}^i & = \frac{(p_1^{q_1 + 1} - 1)}{p_1 - 1} \\ \end{aligned}

Thus follows the proof.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2 

[1] attempted using a similar approach, but WA. Can you point-out any particular case which failed ?


  [1]: https://www.codechef.com/viewsolution/9940392
3

Possibly overflow! As you defined ans to be int type. There might be more errors but this is one of the major errors.

4

Integer overflow. Did cost me 1 WA :’(

5

Wrote a code having time complexity O(n).

I used the fact that, for given an odd number ‘x’, there has to be multiple of the same in range ‘l’ and ‘l+x-1’. Let the ‘l+i be’ that first number in the range ‘l’ to ‘r’, divisible by ‘x’. Therefore we can say that, l+i+x, l+i+2x…< r, will be the divided by ‘x’. Seeing this we can say that, there will be ‘(r-l+1)/x’ or ‘(r-l+1)/x + 1’ numbers divisble by x, depending on the position of first number that is divisble that is divisible by x. We can check that, and add the same to answer.

So, in short we run a loop from i = 1 to i = r, and for every odd ‘i’, we can find number of numbers that are divisible by ‘i’ in O(1) and then multiply the count by ‘i’ and add it to the sum.

You can check my code here.

Thank You.

3 Likes
6

Nice, Just a suggestion: You can count number of multiples of i in range l and r in single line by : r/i - (l-1)/i

7

Yeah. Thanks for that. Good idea! :slight_smile:

8

I used a simple approach. (without using Sieve)

I precomputed fn from 1 to n, just checking all odd numbers from i to sqrt(n) if it is a divisor ??

f[1]=1;

for(i=2;i<100004;i++)
{
    sum=0;
    
    for(j=1;j<=sqrt(i);j++)
    {
        if(i%j==0)
        {
            if(j%2!=0)
                sum+=j;
        
            if((i/j)%2!=0 && j!=sqrt(i))
                sum+=(i/j);
        }
        
    }
        
    f[i]=sum;
}

You can see my solution here


[1].


  [1]: https://www.codechef.com/viewsolution/9938802
9

isn’t the time complexity of seive of erathoneses : O(n*log(log n)). ???

10

Attempted question using a similar approach,but got WA,you can see my


[1] here.Please point out any mistakes?


  [1]: https://www.codechef.com/viewsolution/9962369
11

an easier and a simpler approach according to me would be this–
we take i=1;i+=2

for each odd number between 1 and r we find how many numbers between the given two values(i.e. l and r) are divisible by that number. this would tell us how many times a particular odd number would appear if we sum all the f’s between l and r, we could then multiply this count by that odd number to get their sum.
(idea hint-- remember the childhood ques “how many numbers between 1 and 4000 are divisible by 3” n all…

you can check my code here on this link— link text

12

Solved with d same approach but got WA

13

did it in o(n/2)

14

how to solve the question if the given range is greater than 1e5(around 1e7)…??