007: 「G.C.D」のヒント¶

難易度: ☆

ヒント1

Euclidの互除法では、gcd(a, b) と gcd(b, a % b) が同じ値になることを使います。

ヒント2

a % b は、a を b で割った余りです。余りが0になったとき、そのときの割る数が最大公約数です。

ヒント3

while b != 0: の間、a, b = b, a % b と更新します。ループが止まったときの a が答えです。

ヒント4

gcd(0, b) は b です。この場合も、同じループで処理できます。