Divsum

[dipteshc_sof]

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

[mpr_sof]

http://en.wikipedia.org/wiki/Divisor_function

[swarnaprakash]

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.

[mpr_sof]

Just use the prime factorization of n to compute sigma_1(n). Check out the wikipedia link I pasted before.

[koolman]

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!!!

[swarnaprakash]

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.

[ideamonk]

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 !

[ideamonk]

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;
}

[Yash_sof]

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

[ideamonk]

i was trying prime factorization method

planetmath.org/encyclopedia/Form ... isors.html

i still have a TLE, i need to do some paperwork

[ideamonk]

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);
	}
}

[ideamonk]

and i feel the last code gives wrong answer too

[rahul_goutam]

Just use an O(sqrt(n)) approach.
Run a loop till sqrt(n) and add i and n/i if i is a divisor.

[Robert_Gerbicz]

Just use an O(sqrt(n)) approach.
Run a loop till sqrt(n) and add i and n/i if i is a divisor.

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].

[rahul_goutam]

[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.

[ideamonk]

ya 1.3 sec i got... but i don't like it
can we somehow implement planetmath.org/encyclopedia/Form ... isors.html

in a faster way! because this is a very direct approach.

[rahul_goutam]

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)...

[ideamonk]

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 ?

[arkntos]

#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]

[swarnaprakash]

You don't need to check upto n/2 .See previous posts in this thread and other threads related to this problem for hints.