sgarden problem

please tell me why it is giving me tle,although output and algo is correct
http://www.codechef.com/viewsolution/4326949

for(k=2;k<=n-j+1;k++)
{max=0;
if(primes[k])
{
for(i=1;i<=j;i++)
{count=0;
while((ar[i]%k)==0)
{count=count+1;
ar[i]= ar[i]/k;
}
if(count > max)
max=count;
}

in this code you are running your code for each k,then what is the profit of finding the primes.Try creating a separate array of primes to which has only primes ,nothing else than it will make your loop to go faster…

Also use modular exponentiation to calculate power.

See here.

modular exponentiation is not needed here, my solution got AC w/ .04sec doing just a regular O(n) exponentiation. Using modular exponentiation my solution passed in .04sec as well, so the exponentiation makes no difference here.
a mathematical proof: the biggest prime power would be log(1e6)/log(2)=19, so doing O(n) or O(log n) for n < 19 wouldn’t make the slightest difference

1 Like