Overflow because n\le 10^{12}. Isn’t this O(n\log{n})? Or can you prove that the ranges of equal values allow you to solve it faster?
1 Like
Since the sequence is non-increasing, all similar values should lie together in segments,
so complexity should be O(numberOfSegments), and we know the there can be atmost 2*sqrt(n) segments from here [Tutorial] Math note — Möbius inversion - Codeforces, I don’t know the exact proof.
1 Like
Right… stupid mistake… It works btw.
Yes I realised you were correct. I didn’t realise that at any point, a value can be in at most 2 ranges(Prefix and suffix). But the actual complexity is O(\sqrt{n}\log{n})
1 Like
take MODs in sum functions
2 Likes
it is leading to tle
1 Like
MyExplanation:
If we know m is prime, then we can also use Fermats’s little theorem to find the inverse.
a and m are co-prime..
a^(m-1 )≅ 1 (mod m)
If we multiply both sides with a^(-1), we get :
a^(-1) ≅ a ^(m-2) (mod m)
For calculating the sum of divisors of all the no from 1 to n
We notice that i occurs n/i times in given range 1 to n.
for ( i = 1 to n)
ans += i*(n/i);
But , N = 10^12 so , it gives TLE for O(n) time complexity
So we have to optimize it..
We notice some consecutive no's l , ...., r have same value of n/i = n/r
So we have to take a fast sum of all such intervals and multipy it by n/i
since l , .. r is consecutive so it forms a A.P having difference 1 .
The Only thing we now need to do is to calculate r .
And r can be calculated using :
r = n/(n/l)
ans = 0
for l = 1 to n :
r = n/(n/l) // here we are going to rightmost side of current range..
let us consider some consecutive no's l , ...., r which all have same value for n/l = n/r
(summation of no from l to r *(n/l) ) == (( ( r - l + 1 )*( r + l ))/2)*(n/l) %mod
summation of no from l to r = (( r - l + 1 )*( r + l ))/2 %mod
summation of no from l to r = (( r - l + 1 )*( r + l ))*(2^-1) %mod
summation of no from l to r = (( r - l + 1 )*( r + l ))*binpow(2,mod-2,mod) %mod
binpow(2,mod-2,mod) = mod inverse of 2 . here 2^(-1) == 2^(mod-2) %mod , by fermat little's theorm..
ans += ( (( r - l + 1 )*( r + l )) * binpow(2,mod-2,mod) ) % mod
l = r+1 // here we are going to leftmost value no of next range..My Code:
#include
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define amarks444 \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define line cout << "\n";
#define YES cout <<"YES"<< "\n";
#define NO cout <<"NO"<< "\n";
#define SEE(arr , size) for( ll i = 0 ; i < size ; i++ ) cout<<arr[i]<<" "; cout << "\n";
#define MAXN 1000050
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void solution(){
ll n ;
cin >> n ;
ll ans = 0 ;
for( ll l = 1 ; l <= n ; ){
ll r = n/(n/l);
ans =( ans +(((((( ( r - l + 1 )%mod)*(( r + l )%mod))%mod)*binpow(2,mod-2,mod))%mod)*(n/l))%mod)%mod;
l = r+1;
}
cout<<ans<<"\n";
return;
}
int main()
{
// freopen( "input.txt" , "r" , stdin );
// freopen( "output.txt" , "w" , stdout );
amarks444;
// ll t;
// cin>>t;
// while(t--)
solution();
return 0;
}
the question is not to calculate it for n ; if it was for n upto sqrt n i +n/i etc etc would have been better but i think
initialize sum=0;
for(int i=1;i<=n;i++)
{
sum+=(n/i)*i; (or n-(n%i)) would be better
}
and than cout<<sum%A;
this approach works because no. of integers between 1 to n that are divisible by i are n/i;
long long sumOfDivisors(int N)
{
long long left = 1, sum = 0;
while(left <= N)
{
long long val = N/left;
long long right = N/val;
sum+=(((right*(right+1))/2)-((left*(left-1))/2))*val;
left= right+1;
}
return sum;
}