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

help
, , ,
1

question
question789×472 35.9 KB

How to do this in less than O(n) time?

2

you can go from 1 to sqrt(n)
if divisor
add to sum
if n/i != i
add to sum

3 Likes
3

Approach to do this in less than O(n) time

  1. Initialize sum=0
  2. for(1 to sqrt(n) )
    if(n%i==0)
    {
    sum=sum+i;
    if(n/i!=i)
    sum=sum+n/i
    }
  3. print sum;
2 Likes
4

use this

5

Please find the flaw…This approach gave WA

6

Can you please send the link of the problem?

7

Use long long and also take modulo here res += i .

8

https://cses.fi/problemset/task/1082/

9

done still gives WA

10

Maybe line 13 is incorrect.
If ( n%i == i) // This is never possible.

11

Also, you should return sum of all divisors of all numbers from 1 to n. You are returning sum of divisors of only n.

1 Like
12

This will lead to TLE, wouldn’t it?

13

It’s just \sum_{i=1}^n i\lfloor n/i\rfloor Since i divides \lfloor n/i \rfloor values less than n.
To optimise this we can notice that \lfloor n/i\rfloor goes through only O(\sqrt{n}) values.
n/j is i for j\in (\lfloor n/(i+1) \rfloor, \lfloor n/i \rfloor \ ]

My code 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p =1e9 +7;
void solve(){
    ll n;
    cin>>n;
    ll ans=0;
    auto sumtill= [&](ll x){
       x%=p;
       ll sum=x*(x+1);
       sum%=p;
       sum*=(p+1)/2;
       sum%=p;
       return sum;
    };
    for(ll i=1;i*i<n;i++){
        if(i==n/i){
            continue;
        }
        ans+= n/i * i;
        ans%=p;
    }
    for(ll i=1;i*i<=n;i++){
        ans+=(sumtill(n/i) - sumtill(n/(i+1)))*i;
        ans%=p;
    }
    cout<<ans<<'\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
5 Likes
14

Can you elaborate more on this please. I didn’t get the idea. More over, how’d you come up with the formula. Please share links.

Thank you!

15

Instead of thinking in terms of the sum of divisors of this number, you can think how many numbers i divides that are less than n. It’s pretty easy to see that there are \lfloor n/i \rfloor such numbers.

1 Like
16
  1. Do prime factorisation of N
  2. N = a^( p ) * b^( q ) * c^( r ) …
  3. sum_of_factors = [(a^(p+1)-1)/(a-1))] * [(b^(q+1)-1)/(b-1))] * [(c^(r+1)-1)/(c-1))]…
2 Likes
17 
#include<bits/stdc++.h>
using  namespace std;
#define lli long long int
int main(){
 lli n;
 cin>>n;
 lli tt=1;
 for(lli i=2;i*i<=n;i++){
    lli val = i;
    lli deno = i;
    lli f=0;
    while(n%i==0){
      val = val*i;
      n/=i;
      f=1; 
    }
   // cout<<n<<" "<<((val-1)/(deno-1))<<endl;
    if(f)
      tt = tt * ((val-1)/(deno-1));
  }
  if(n>1)
    tt = tt*((n*n -1)/(n-1));
cout<<tt<<endl;

return 0;
}
18

People have been posting about getting the sum of divisors of a single number N in time O(\sqrt N) time, but what I read is that you need the sum of divisors of all numbers \le N in O(\sqrt N) time.

Well, the answer is \sum_{i=1}^N i\cdot \lfloor\frac N i\rfloor. We can notice that the sequence \lfloor\frac N 1\rfloor, \lfloor\frac N 2\rfloor, \dots, \lfloor\frac N N\rfloor has at most 2\sqrt N different values. Indeed, since \lfloor\frac N i\rfloor\ge \lfloor\frac{N}{i+1}\rfloor, we can split the sequence in O(\sqrt N) intervals l_i \dots r_i such that in the interval i all \lfloor\frac N j\rfloor are equal to \lfloor\frac{N}{l_i}\rfloor, so the answer is:

\sum_{\text{all intervals } [l_i\dots r_i]}( r_i-l_i+1)\cdot \lfloor\frac{N}{l_i}\rfloor

Since there are O(\sqrt N), the time complexity of this solution is O(\sqrt N).

5 Likes
19

nope.In the worst case also, when n=10^12 no. of iterations will be 10^6.

1 Like
20

Bro please explain this…i m not able to understand this thing .
I go to CF_LINK but i m not able to understand same thing