Page 3 of 3
Posted: Sat Apr 22, 2006 5:16 am
by Timo
For IRA
Code: Select all
#define I long long
I CSOD(I n)
{
I i,out2=0,j=sqrt(n);
for(i=2;i<=j;i++) out2 += (n/i)*i; // O(sqrt(n))
for(i--;j>=1;j--) { out2 += (j*sum(i+1,n/j)); i=(n/j); } // O(sqrt(n))
// last operation before return only take O(1)
return out2;
}
if see my snippet code maybe you can understand why the time complexity is O(sqrt(n))
don't use my snippet code to be part of your program,
my snippet code is wrong because I don't write the last operation that
consume O(1) before return out2.
Hope it help you
Posted: Sun Apr 23, 2006 5:24 am
by IRA
Code: Select all
#define I long long
I CSOD(I n)
{
I i,out=0,j=sqrt(n),k=n/2;
for(i=2;i<=j;i++)
out += (n/i)*i; // O(sqrt(n))
j=n/(j+1);
for(;j>=2;j--) { out += (j*((i+n/j)*(n/j-i+1)/2)); i=n/j+1; } // O(sqrt(n))
out=out-????????????????????????????????????????;
return out;
} }
I think that I have know your method.
Thanks, Timo
========================================
I already got AC!
still TLE
Posted: Mon Jan 08, 2007 2:03 pm
by sethos
Hi,
This is a very nice problem, but i thought it would be easier...
i came to allmost the same formula as mentioned here in the forum, but i allways get TLE
here is my code: where can i optimize it?
Code: Select all
#include <iostream>
#include <math.h>
#include<string>
#include <stdlib.h>
#include<algorithm>
#define I long long
using namespace std;
int main()
{
long inp, n ;
for(int i=1; i<200; i++){
cin >> n;
if(n == 0) break;
I total = 0;
for(I t=2; t<n; t++){
total+=(n/t)*t-t;
}
cout <<"Case "<<i<<": "<< total << "\n";
}
return 0;
}
Posted: Mon Jan 08, 2007 11:47 pm
by Jan
Your complexity is O(n), you can reduce it to O(sqrt(n)).