テクノロジ系
秋期
応用情報技術者 2015年 秋期 問6
6 / 80
次に示すユークリッドの互除法(方法 1,方法 2)で、正の数a,6の最大公約 数は、それぞれmとれのどちらの変数に求まるか。ここで、m modnは、mをnで 割った余りを表す。 方法1 方法 2
正解と解説
表示する
正解 ウ
n m
ユークリッドの互除法では、m mod nの繰り返しでnが0になる直前の値、あるいは剰余を代入していく変数に最大公約数が残ります。方法1・方法2それぞれの記述に従うと、最大公約数はnとmに求まる組合せが正解です。