×

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

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


}

5★s1d_3
165413
accept rate: 20%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×796
×263
×74

question asked: 05 Feb '14, 11:25

question was seen: 711 times

last updated: 06 Feb '14, 10:26