DouKaku? 4787 shiro: この回答が破綻するのは一方が他方よりはる...(最大公約数（除算禁止）)

Comment detail

This comment is reply for 4786 186: 出題者です. >隣り合うフィ...(最大公約数（除算禁止）). Go to thread root.

この回答が破綻するのは一方が他方よりはるかに大きな場合ですね。m >> n で m = q*n + rのとき n >> r になるような組み合わせを続けてゆくと減算のみによる方法では悲惨なことに。

減算を繰り返して割り算の代わりにする方法だと差が大きいときに問題になる、ということで 「文字列の長さをみて小さい側を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)