Product of divisors - TLE

general
,
1

Hi…I am a newbie at codechef…so i was practicing an easy program D1 given in the codechef site for calculating product of divisors…but the online judge keeps giving me the error “time limit exceeded”…can you help me in optimising the problem?

#include<iostream>
using namespace std;
int main()
{
    unsigned long N, t=1;
    int i;
    cin>>N;
    unsigned long *a=new unsigned long [N];
    unsigned long *b=new unsigned long [N];
    for(i=0; i<N; i++)
    scanf ("%d", a+i);

    for (int j=0; j<N; j++)
    {
        for(int k=1; k<a[j]; k++)
        {
			if (a[j]%k==0)
			t=t*k;
			if(t>9999)
			t=t%10000;
		}
		b[j]=t;
		t=1;
	}

	for(int y=0; y<N;y++)
		printf("%.4d\n", b[y]);

	delete []a; delete []b;
}
2

You have to realize that your code has O(MAXT*MAXN) complexity, so for the boundaries from statement (MAXT = 300.000 and MAXN = 500.000) it’s too much…

3

there is a tutorial for this question: http://blog.codechef.com/2009/08/17/tutorial-for-problem-product-of-divisors/

~look at the variable constraints, it will give you a good idea of what kind of complexity you will need, and it will save you time from coding algorithms exceeding this complexity ^^

1 Like