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 と答えることになります。