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

help
, , ,
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