【Python】約分する関数

gcdをPythonの標準ライブラリに見つけた。
自分で書いても全然いいけど、あるから使っておこう。

GoogleCodeJam の Round 1Cで約分をする必要がある問題がでてた。
p / q を約分する関数

計算量は O (log min(p, q))

ちなみにPythonのgcdの実装

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a