Namaran

Code daily. Without assist.

2026-08-29

gcd_steps.rs

fn main() {
    let (mut a, mut b) = (21u32, 13u32);
    let mut steps = 0;
    while b != 0 {
        (a, b) = (b, a % b);
        steps += 1;
    }
    println!("{a} {steps}");
}

これは何を出力するでしょうか?

Answer

1 6 です。

(a, b) = (b, a % b) は、右辺のタプルを古い a と b で作り終えてから、その2つの値を左辺の a と b へ書き込みます。a % b を計算する時点で a はまだ書き換わっていないので、1回ごとに組が「b と、a を b で割った余り」に置き換わります。

組は (21, 13) から (13, 8)、(8, 5)、(5, 3)、(3, 2)、(2, 1)、(1, 0) と6回変わります。余りは割る数より必ず小さいので、b は1回ごとに真に減ります。0以上の整数は限りなく減り続けられないので、このループは必ず止まります。b が0になった時点の a は 1 で、これは21と13の最大公約数です。

a = b; と b = a % b; を1文ずつ順に書いたと読むと、2文目の a はもう 13 なので b は 13 % 13 で0になり、13 1 と答えることになります。