HI Everyone.
I am trying to solve this problem 14122. Inverse of Recurrence Problem With a Square Root but getting TLE. I am not very good at python but somehow manage to write this code.
Please help me. Can someone suggest me fast input methods in python.
Problem link:http://www.spoj.com/problems/IRECSQRT/
import math
import sys
write = sys.stdout.write
f1 = [[0]*3 for x in range(3)]
f2 = [[0]*3 for x in range(3)]
_CUTOFF = 200
def multiply(x, y):
if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF: # Base case
return x * y;
else:
n = max(x.bit_length(), y.bit_length())
half = (n + 32) // 64 * 32
mask = (1 << half) - 1
xlow = x & mask
ylow = y & mask
xhigh = x >> half
yhigh = y >> half
a = multiply(xhigh, yhigh)
b = multiply(xlow + xhigh, ylow + yhigh)
c = multiply(xlow, ylow)
d = b - a - c
return (((a << half) + d) << half) + c
def multiplyy(n,m):
r1 = [[0]*3 for x in range(3)]
r2 = [[0]*3 for x in range(3)]
if n==0:
for i in range(0,3):
for j in range(0,3):
r2[i][j]=f1[i][j]
if n==1:
for i in range(0,3):
for j in range(0,3):
r2[i][j]=f2[i][j]
for i in range(0,3):
for j in range(0,3):
for k in range(0,3):
r1[i][j]+= multiply(f1[i][k],r2[k][j])
for i in range(0,3):
for j in range(0,3):
if r1[i][j]>=0:
f1[i][j]=r1[i][j]
if f1[i][j] >=m:
f1[i][j]=f1[i][j]%m
else:
f1[i][j]=-1*(-1*r1[i][j])%m
def power(n,m):
if ( n==0 or n==1 ):
return
power(n//2,m)
multiplyy(0,m)
if n%2!=0 :
multiplyy(1,m)
def invfunction(n,m):
f1[0][0]=7
f1[0][1]=-14
f1[0][2]=8
f1[1][0]=1
f1[1][1]=0
f1[1][2]=0
f1[2][0]=0
f1[2][1]=1
f1[2][2]=0
f2[0][0]=7
f2[0][1]=-14
f2[0][2]=8
f2[1][0]=1
f2[1][1]=0
f2[1][2]=0
f2[2][0]=0
f2[2][1]=1
f2[2][2]=0
if n==0:
return 1
elif n==1:
return 2
elif n==2:
return 5
else:
power(n-2,m)
ans=( f1[0][0]*5 + (f1[0][1]<<1) +f1[0][2] )
if ans >=m:
return ans%m
else:
return ans
def IRECSQRT():
tc=int(sys.stdin.readline())
while tc :
n,m=sys.stdin.readline().split(" ")
n=int(n)
m=int(m)
finalans=invfunction(n,m)
print(finalans)
tc-=1
IRECSQRT()
