DouKaku? 4788 にしお: 減算を繰り返して割り算の代わりにする方法...(最大公約数（除算禁止）)

Comment detail

This comment is reply for 4787 shiro: この回答が破綻するのは一方が他方よりはる...(最大公約数（除算禁止）). Go to thread root.

減算を繰り返して割り算の代わりにする方法だと差が大きいときに問題になる、ということで 「文字列の長さをみて小さい側を10**n倍する」 という荒技を使ってみました。

# Screencast-o-maticで撮りながら作ったのにアップロード中にブラウザが落ちて消滅…orz

def gcd(x, y):
    if x == y: return x
    if x < y: y, x = x, y

    lx = len(str(x))
    ly = len(str(y))
    diff = lx - ly

    z = abs(y * 10 ** diff - x)
    z2 = abs(y * 10 ** (diff + 1) - x)
    z = min(z, z2)
    if diff > 0:
        z2 = abs(y * 10 ** (diff - 1) - x)
        z = min(z, z2)

    # zはxとyと公約数を共有する
    if z < y:
        return gcd(y, z)
    return gcd(z, y)