Hello. I can't solve this problem https://www.spoj.pl/problems/VGCD. Im trying to solve it using Python, but, I'm newbie in Python, so, I don't know if I am implementing the code as fast as possible.
Here is my code:
from cStringIO import StringIO
from sys import stdin
import psyco
psyco.full()
def multiply(v, w):
return [
[
v[0][0] * w[0][0] + v[0][1] * w[1][0],
v[0][0] * w[0][1] + v[0][1] * w[1][1]
],
[
v[1][0] * w[0][0] + v[1][1] * w[1][0],
v[1][0] * w[0][1] + v[1][1] * w[1][1]
]
]
def power(v, n):
if (n == 0):
return [[1, 1], [1, 1]]
if (n == 1):
return v
res = power(v, n / 2)
res = multiply(res, res)
if (n & 1):
res = multiply(res, v)
return res
def bsearch(fib):
i = 0
j = 60010
while (i + 1 < j):
m = (i + j) / 2
v = power([[0, 1], [1, 1]], m)
if (v[1][1] == fib):
return m + 1
elif (v[1][1] < fib):
i = m
else:
j = m
return i
def gcd(a, b):
if (b == 0):
return a
return gcd(b, a % b)
text = StringIO(stdin.read()).readlines()
i = 1
out = ""
for i in range(1, len(text), 2):
n = long(text[i])
m = long(text[i + 1])
v = power([[0, 1], [1, 1]], gcd(bsearch(n), bsearch(m)) - 1)
out += "%s\n" % v[1][1]
print out
I'm getting Time Limit Exceeded with 0k, I think is caused by the line "text = StringIO(stdin.read()).readlines()". But I don't know any other way of speeding I/O in Python. Can someone help me? Thanks.