Can someone give me an efficient algorithm for the DIVSUM problem?? I have been trying it for quite sometime now but always I have got a TLE error. Someone please help
created
Feb '08last reply
Oct '23- 24
replies
- 2.0k
views
- 12
users
- 3
links
If k is a divisor of n then n/k is also a divisor of n. Using this you can try a simple O(sqrt n) approach to get AC.
Another approach is precalculating all values upto max_input in a sieve.
Just use the prime factorization of n to compute sigma_1(n). Check out the wikipedia link I pasted before.
17 days later
Hello everybody...
I used the following algorithm fo the DIVSUM problem...
i64 ans = 0;
void sum ( i64 n )
{
for ( i64 i = 2 ; i <= floor(sqrt(n)) ; i ++ )
{
if ( n%i == 0 )
{
if ( n/i == i )
ans += i;
else
ans += i + (n/i);
}
}
cout << ans+1 << endl;
}
But I m getting TLE for the above algorithm...
Anybody pls help me!!!
I wish to know is there optimization to be done here....
Also pls tell me , if there is any other efficient algorithm apart from this....
Thanks a lot in advance!!!
Do not use long long int unless it is necessary.They are very slow.
In this problem everything fits in int.
Do not use floor(sqrt(n)) inside a loop because each time the loop is run it would calculate the square root and that alone would cause TLE.Compute before and store it in a variable.
Also you can check the special condition outside the loop. 
3 months later
I learnt some combinatorics, and tried my best
#include <iostream>
#include <deque>
using namespace std;
int p[127]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709};
int sieve[500001];
class dynamite{
int counter, current, period,start, end, retval;
public:
void set(int s,int e,int p){
start = s;
end = e;
period= p;
counter=0;
current = start;
}
int gen(){
retval = current;
counter++;
if (counter>=period){
counter=0;
current++;
if (current>end)
current=start;
}
return retval;
}
};
main(){
int n,test,i,isprime,sum=0,cnum,cpow,period;
int firstmatch;
float test2;
deque<int> pfacs,powers;
cin >> n;
// make the sieve
for (int i=2;i<=709;i++)
sieve[i]=0;
for (int i=710;i<=500000;i++)
sieve[i]=1;
for (int i=0;i<127;i++)
sieve[p[i]]=1;
// extend the sieve
for (i=0;i<127;i++){
firstmatch=500001;
for(int j=710;j<=500000;j++){
if (j%p[i]==0){
firstmatch=j;
break;
}
}
while (firstmatch<=500000){
sieve[firstmatch]=0;
firstmatch+=p[i];
}
//all factors of p[] made zero
// now sieve has 1 for primes till 500000
}
while (n--){
cin >> test;
// final combinatorial calculation
sum=1;
// build list of prime factors and corresponding powers
for (i=2;i<=test;i++){
if (sieve[i]){
if (test%i == 0){
pfacs.push_back(i);
cpow=0; cnum=test;
while(cnum%i == 0){
cnum = cnum/i;
cpow++;
}
powers.push_back(cpow);
}
}
}
sum=0;
period=1;
// decide number of dynamites
if (1){
dynamite d[pfacs.size()];
d[0].set(0,powers[0],period);
for (int i=1;i<pfacs.size();i++){
period*=powers[i-1]+1;
d[i].set(0,powers[i],period);
}
int lim=period*(powers[powers.size()-1]+1);
int prod;
for (int i=0;i<lim;i++){
prod = 1;
for (int j=0;j<pfacs.size();j++){
int p1=d[j].gen();
for (int x=0;x<p1;x++)
prod *=pfacs[j];
}
sum+=prod;
}
cout <<sum-test <<endl;
}
pfacs.clear();
powers.clear();
}
}all i get is a TLE !!!
but for input of
1
500000 its pretty fast !
i removed deques
reduced the code
still getting TLE
should i make the prime sieve faster ? as done in prime1 problem?
#include <iostream>
#include <math.h>
using namespace std;
int p[127]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709};
int sieve[500001];
main(){
int n,test,i,isprime,sum=0,cnum,cpow,term;
int firstmatch;
float test2;
cin >> n;
// make the sieve
for (int i=2;i<=709;i++)
sieve[i]=0;
for (int i=710;i<=500000;i++)
sieve[i]=1;
for (int i=0;i<127;i++)
sieve[p[i]]=1;
// extend the sieve
for (i=0;i<127;i++){
firstmatch=500001;
for(int j=710;j<=500000;j++){
if (j%p[i]==0){
firstmatch=j;
break;
}
}
while (firstmatch<=500000){
sieve[firstmatch]=0;
firstmatch+=p[i];
}
//all factors of p[] made zero
// now sieve has 1 for primes till 500000
}
while (n--){
scanf ("%d",&test);
// final combinatorial calculation
// build list of prime factors and corresponding powers
cnum=test;
sum=1;
for (i=2;i<=test && cnum>=2;i++){
if (sieve[i]){
if (test%i == 0){
cpow=0;
term=1;
while(cnum%i == 0){
cnum = cnum/i;
cpow++;
term += pow(i,cpow);
}
sum*=term;
}
}
}
printf ("%d\n",sum==test ? 1:sum-test);
}
return 0;
}
You are unnecessarily complicating the thing ... 
You can do that with a very small 15 line code 
The idea is as follows --
Let the number be n .. then let k = n/2 + 1 .
Now you need to run only a loop for 2 to k and also modify the value k in the loop . Don't Read Ahead if u want to think more.
To put plainly if (n%i) == 0 ,, then i and n/i both are divisors of n .
Also there can't be a divisor greater than k/i after each run , so we can change k to k/i.I Hope it Helps.
Best Regards,
Yash
i was trying prime factorization method
planetmath.org/encyclopedia/Form ... isors.html1
i still have a TLE, i need to do some paperwork
GSHHHHHH even this doesnt work...
I will give it a fresh thought tomorrow...
#include <iostream>
using namespace std;
main (){
int n,t,sum,k,i;
scanf ("%d",&n);
while (n--){
scanf ("%d",&t);
sum=1;
k=t/2 + 1;
i=2;
while (i<k){
if (t%i==0){
sum += i + t/i;
k=k/i;
}
i++;
}
printf ("%d\n",sum);
}
}
There are lots of input numbers so it would be possible to get TLE by your method.
You can compute sigma(k) for all k up to n in O(n*log(n)) time and using
O(n) memory (it was my original solution, it takes about 0.84 sec.), but also
in O(n*log(log(n))) time. And you can get probably a nice improvement, if
you use fread/fwrite for fast input/output, because there are large amount of
input/output in the program. [Note that the answer is sigma(n)-n if the input=n].
[quote="Robert Gerbicz"]
There are lots of input numbers so it would be possible to get TLE by your method.
/quote]
No, I got acc. in 1.3s using scanf,printf.
ya 1.3 sec i got... but i don't like it
can we somehow implement planetmath.org/encyclopedia/Form ... isors.html5
in a faster way! because this is a very direct approach.
I tried using that formula..
what I do is calculate and store all primes first.
Then check for the prime divisors of the input number.
which is pretty simple but unfortunately TLE
Can't think of any O(nlogn)approach to precalculate all values and store as Robert said (and too sleepy to think right now)...
if t is power of 2, sigma(t)-t = t-1
[code]if ( (t&(t-1))==0 ){
printf ("%d\n",t-1);
continue;
}[/code]i was hoping this would cut down on calculations and make prog faster, but still i get 1.3 sec. why doesn't this step optimize the processs ?
26 days later
#include<stdio.h>
int main()
{
int N;
int n,count=0 , last,fac,i,k; // make it unsigned
scanf("%d",&N);
for (k = 0; k < N ; k++)
{
scanf("%d",&n);
count = 1;
last = n/2;
i = 2 ;
while(i < last)
{
if ((n%i)==0)
{
last=n/i;
count = count + i + last ;
}
i++;
}
if (--i == last ) count-=i;// If factors are same
printf("%d\n",count);
}
}
This too TLE . I have been cutting corners but no use. .
:([code][/code]