Sum of divisors of all numbers less than n in less than O(n) time

help
, , ,
21

@nishant403 help me in this too :pray:

22

Read The harmonic lemma from this blog.

1 Like
23

Explanation : Instead of finding number of divisors for a number, we find how many times a number comes as a divisor which is the same thing. So an integer ‘i’ comes as a divisor, for i,2i,3i,…m*i and m is floor ( n/i ).

Maybe now you can get the formula stated above.

2 Likes
24

Refer to this link for better understanding Number of divisors / sum of divisors - Algorithms for Competitive Programming. Also you can use binary_exponentiation to reduce time complexity.

25

yeah bro i got that point eariler too… but how can i do this in root(N) complexity …

As u share link i understand floor(n/i) have atmost 2*root(n) distinct values …but how can i find sum of all divisiors in root(N) ?

26

Read little further in that blog it is given.

1 Like
27 
#include <iostream>

using namespace std;

int main() {
    int la;
    int n=10000,cnt=0;
    for (int i = 1, la; i <= n; i = la + 1) {
	la = n / (n / i);
	cout<<la<<" ";
	//n / x yields the same value for i <= x <= la.
	cnt++;
}
cout<<endl<<cnt;
}

This code demonstrate what are the different values of floor(n/i) will be… but then how can i find sum ?

28

Yeah correct lets take an example N = 16
for i=1 to 16 floor(N/i) will be
16 8 5 4 3 2 2 2 1 1 1 1 1 1 1 1
for 1 the interval is 9-16
for 2 the interval is 6-8
for 3 the interval is 5-5
for 4 the interval is 4-4
for 5 the interval is 3-3
for 8 the interval is 2-2
for 16 the interval is 1-1
But how to find this interval in O(root(N)) ?

1 Like
29

Ok, look: let’s define the i^{th} interval by [l_i\dots r_i].

Well: l_1=1 and l_i=r_{i-1}\ \forall i > 1. How to compute r_i?

We can Binary Search it, but we can also do it with simple math.
We now that:

\lfloor\frac{N}{r_i}\rfloor=\lfloor\frac{N}{l_i}\rfloor\rightarrow \frac{N}{r_i} \ge \lfloor\frac{N}{l_i}\rfloor\rightarrow r_i=\lfloor\frac{N }{ \lfloor\frac{N}{l_i}\rfloor}\rfloor.

So, the code is something like this:

  for(int l=1; l <= n;){
       int r = n/(n/l);
       ans += (long long)(r-l+1)*(long long)(n/l);
       l = r+1;
    }
3 Likes
30

I thought it should be easy to follow now.

You have to compute this :

for i =1 to N
ans += i*floor(N/i)

Now you are given, floor(N/i) is same for some interval i to la ,so you can compute it as,
(N/i)( i + (i+1) + … + la)

Is this clear now ?

2 Likes
31

I understand this –

But explain this with example …

For ex : N = 16
la = 1 2 3 4 5 8 16

32

Let’s take a small example given in the question :
N = 5 for that,

values of i and la will be , (1,1) , (2,2) , (3,5)
so answer is, (5/1)(1) + (5/2)(2) + (5/3)*(3 + 4 + 5) = 21

5 Likes
33

Now I got it… both the solutions @nishant403 @aniervs thank you so much :slight_smile: :100:

35

what is modulo 10^9 + 7

36

This means you have to take modulus for the given number. When answer is big, it is done.
eg- Your result is val. Then you should give val%mod where mod=1e9+7

37

all of your code make sense to me, but what does this statement do ?

38

Modular inverse of 2.

1 Like
39

divide by constant to get O(logN)

40

It is possible in the case n is perfect square n = 16 and i = 4, so we don’t need to count 2 divisors here. but only 1.

41

I this tried using Divide and Conquer but getting WA for a few TCs:

int n;

int sum(int a,int b){
    return (b*(b+1)/2-a*(a-1)/2);
}

int f(int i,int j){
    if(n/j==n/i)return (sum(i,j)%MOD*(n/j)%MOD)%MOD;
    int mid=(i+j)/2;
    return (f(i,mid)+f(mid+1,j))%MOD;
}

signed main(){
    FASTER;
    cin>>n;
    cout<<f(1,n);
}

Can you tell whats wrong ?
anyone ?