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

general
1

code is in
CodeChef: Practical coding for everyone 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)
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

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 - XPeYLR - Online Python3 Interpreter & Debugging Tool - Ideone.com

3

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

4

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…