getting TLE for chef and segments even after calculating mod using repeating square method in python!

code is in
http://www.codechef.com/viewsolution/2531229 or

``````n = int(input())
a = list(map(int,input().split()))
b=a
t = int(input())
primelist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
pfreq=[[0 for i in range(25) ]for j in range(n)]
def modular_pow(base, exponent, modulus): # algorithm understood and applied from  wikipedia
result = 1
while exponent > 0:
if (exponent % 2 == 1):
result=(result*base)%modulus
exponent = exponent>>1
base = (base * base)%modulus
return result

while t>0:
t-=1
c = list(map(int,input().split()))
for i in range(0,n):
for prime in primelist:
if a[i]%prime==0:
while a[i]>0:
ind = primelist.index(prime)
pfreq[i][ind]+=1
a[i] = a[i]//prime
if a[i]%prime==0:
continue
else:
a[i]=b[i]
break
rem=1
for i in range(0,25):
exp=0
for j in range(c[0]-1,c[1]):
exp+=pfreq[j][i]
#rem = (rem*pow(primelist[i],exp,c[2]))%c[2]
rem*=modular_pow(primelist[i],exp,c[2])
rem = rem%c[2]
print(rem)``````

I’m not using python at all, but I’m afraid it’s too slow (I/O operations) for that problem, worst case (largest input) is

``````100000
100 100 ... 100
100000
100000 100000 1000000000
100000 100000 1000000000
...
100000 100000 1000000000
``````

~2.7MB you have to read in 1 second, try to read all the data without printing single line of input. If you get WA it’s quick enough, if you get TLE, probably I’m right…

edit: your code is slow, it didn’t finished on IdeOne in 5s for a lot smaller input…

even 15 seconds is not enough - http://ideone.com/XPeYLR

@betlista that won’t help. There are smaller test files. When a WA is obtained on that, it will be reported. We may never know, whether our pgm was even given the large file as input.

In the meantime, what you can try is to create the large test file on your system, and run your pgm locally, to see the time taken.

Python is inherently slower than other languages. I would recommend using a faster language (like C/C++) for such problems.

You are correct, there is not simple way. Maybe he can run program for let say N <= 20.000 and T <= 20.000, ore I’ll try on IdeOne…

//