def power(m,n,x):

temp=power(m,n/2,x)

if n%2 == 0:

return (temp%x*temp%x)%x*

else:

return (mtemp%x*temp%x)%x

t=int(input())

g=1298074214633706835075030044377087

while(t):

t=t-1

p=int(input())

print (power(2,p+1,g)-1)%g

the code when compiled gives runtime error …saying eof when reading a file…

plz… tell me how to overcome this … i’m new to python

how are you providing the input…i.e. in what format…can u give an example on ideone!!!

input is simply

first enter the no. of test cases… n then enter p … i.e the power of two to b calculated…

see this link…ideone link…i just added the terminating condition as it was entering an infinite recursion which was creating the RE…hope this helps…

hey but now the code gives tle

i think TLE is caused because ur algo is O(log(n)) per test case…i.e. total time complexity is O(T*log(n))…instead precompute all the values which will take and then print the required values per test case with a complexity of O(1)…i.e. total complexity will be the time required to precompute…which takes linear time…which is lesser than the previous algo…hope this helps…

also avoid doing so many modulo operations as it is very slow…also python can handle large integers so lesser modulo operations will not lead to overflow!!!

o.k… i also thought the same …

but can u give me the syntax in python… how should i precompute… python is new to me

powers_of_2 = [str(1<<i) for i in range(500)]

t=int(input())

while(t):

t=t-1

p=int(input())

if(p==0):

print “1”

else:

print (powers_of_2[p+1]-1)%1298074214633706835075030044377087

hey… i’m done with precomputation … still that eof

this is your corrected solution…http://ideone.com/N8rnU3 . 2 mistakes…1 is improper indentation and second is the time complexity again…for every n u are calculating 2^n which makes the complexity even worse…O(n^2)!!!

1 Like

Fix the indentation ,avoid unnecessary type casting . In python 2.7 you can just use `input()`

without type casting to take the integer input. Also `power_of_2`

is a list of strings. So, the print statement inside the else block will raise a TypeError