sgarden problem

general
1

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

2

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.

3

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