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