# 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[i]=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[i]]=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[i]]=nProduct;

}

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

printf("%ld\n",Output[Input[i]]);
``````

}

//