19/09/01 12:59:15.63 vep5FkUD.net
>>371
100までの2つの異なる正の数を選んだとき，その最大公約数は必ず
100の半分の50以下となる．
（証明）
2つの数は片方が50以下，または
2数の差が50以下のいずれかを満たす．
前者ならば自明．
後者ならばユークリッドの互除法により成立．
これを踏まえて，以下の方法をとれば
回数は最小となる．
50以下の残った数のうち最大のものを選び，
これが最大公約数となるよう2数を決定する．
2数とそのすべての公約数を除く．
繰り返して50以下の数がなくなったら，
任意の2数を選び繰り返す．
具体的には
50-100 49-98 ... 26-52 51-53 55-57 ... 97-99