Product of Divisors - Time exceeded. Used efficient algos.

Link to the question - http://www.codechef.com/problems/D1/

Link to my solution - http://www.codechef.com/viewsolution/3335258

I have used a simple and efficient code. Have used as many time-cutters as possible. I cannot hink of any other possible method. I have been engaged in this since yesterday afternoon. Could somebody help me out here please?

Do I have to use memoization for each pair (N,pwr) that I encounter as well? It will be a lengthy procedure and will take up a lot of memory and I am not sure it will work as well. Is there something simple I am missing?

#include

#include

using namespace std;

long int myPow(long int N, long int Pwr)

{

N%=10000;

if(N==0 || N==1)

	return N;

else if(Pwr==1)

	return N;

else if (Pwr==0)

	return 1;

while((Pwr%2)==0)

{

	N*=N;

	N%=10000;

	if(N==0 || N==1)

		return N;

	Pwr/=2;

}

long int A=N*(myPow((N*N),(Pwr-1)/2));

return (A%10000);

}

int main()

{

long int i, j, x, T, N, temp, nProduct, nDivisors, nPrimeCount=2, Primes[100000], nFactCount;

int Output[500001]={0};				// using open-addressing to check for repeated test-cases

Primes[0]=2;

Primes[1]=3;

scanf("%ld",&T);

long int nLength, Input[T];

for(i=5;i<=250000;i+=4)				// Creating an array of all primes <=250000. Cheking for 6n-1 and 6n+1

{

	for(j=2;j<=sqrt(i);j++)

		if((i%j)==0)

			break;

	if(j>sqrt(i))

		Primes[nPrimeCount++]=i;

	i+=2;

	for(j=2;j<=sqrt(i);j++)

		if((i%j)==0)

			break;

	if(j>sqrt(i))

		Primes[nPrimeCount++]=i;

}

for(i=0;i<T;i++)				// O(T*nprimeCount) loop

{

	scanf("%ld",&N);

	if(Output[N]>0)

		continue;

	Input*=N;

	temp=N;

	nProduct=1;

	nDivisors=1;

	j=0;

	x=2;

	while((x<=(N/2)) && (temp!=1))		// O(nPrimeCount) loop.	// Did not include N here.

	{

		nFactCount=1;

		while((temp%x)==0)

		{

			nFactCount++;

			temp/=x;

		}

		nDivisors*=nFactCount;

		j++;

		x=Primes[j];

	}

	if(temp==N)				// when N is PRIME

	{

		Output[Input*]=1;

		continue;

	}

	nDivisors-=2;				// Removing the 2 cases for 1 and N as divisors, as N is NOT prime

	temp=sqrt(N);

	if((temp*temp)==N)			// if square, we muliply by root and remove the element from No. of divisors

	{

		nDivisors--;

		nProduct*=temp;

	}

	nProduct*=myPow(N,(nDivisors/2));

	nProduct%=10000;

	Output[Input*]=nProduct;

}

for(i=0;i<T;i++)

	printf("%ld

",Output[Input*]);

}