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

code is in or

n = int(input())
a = list(map(int,input().split()))
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):
            exponent = exponent>>1
            base = (base * base)%modulus
    return result
while t>0:
    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)
                    a[i] = a[i]//prime
                    if a[i]%prime==0:
    for i in range(0,25):
        for j in range(c[0]-1,c[1]):
        #rem = (rem*pow(primelist[i],exp,c[2]))%c[2]
    rem = rem%c[2]

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

100 100 ... 100
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 -

@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…