done still gives WA
Maybe line 13 is incorrect.
If ( n%i == i) // This is never possible.
Also, you should return sum of all divisors of all numbers from 1 to n. You are returning sum of divisors of only n.
This will lead to TLE, wouldn’t it?
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();
}
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!
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.
- Do prime factorisation of N
- N = a^( p ) * b^( q ) * c^( r ) …
- sum_of_factors = [(a^(p+1)-1)/(a-1))] * [(b^(q+1)-1)/(b-1))] * [(c^(r+1)-1)/(c-1))]…
#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;
}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).
nope.In the worst case also, when n=10^12 no. of iterations will be 10^6.
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
Read The harmonic lemma from this blog.
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.
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.
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) ?
Read little further in that blog it is given.
#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 ?