You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

}

asked 05 Feb '14, 11:25

s1d_3's gravatar image

5★s1d_3
165413
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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