Greatest Common Divisor

共通の約数は、2つの数のうち小さい方より大きくなることはありません。なぜなら、bの約数は最大でもbだからです。そこで、候補となるdをmin(a, b)から始め、両方を割り切るまで1ずつ減らします。候補を大きい方から試すため、条件を満たす最初のものが最大公約数です。

12と18の場合、12（18を割り切らない）、次に11、10、9、8、7を試しますが、どれも条件を満たさず、6で終了します。1はすべての数を割り切るため、ループは必ず終了します。

計算量は候補の数に比例します。2つの素数である999999937と999999929の場合、答えは1で、ループはほぼ10^9回実行されます。最大規模のテストには遅すぎます。

r = a % b となるように a = q × b + r と書きます。a と b の両方を割り切る数は、r = a - q × b も割り切ります。b と r の両方を割り切る数は、a = q × b + r も割り切ります。したがって、組 (a, b) と (b, r) は、まったく同じ公約数を持ち、最大公約数も同じです。

(a, b) を (b, a % b) に置き換え、b が 0 になるまで繰り返します。すべての数は 0 を割り切るので、gcd(a, 0) = a となり、a が答えです。12 と 18 の場合、(12, 18) は (18, 12)、次に (12, 6)、さらに (6, 0) となり、答えは 6 です。最初のステップで、小さい方が a の場合は自動的に数値が入れ替わるため、並べ替える必要はありません。

2ステップごとに大きい方の数は少なくとも半分になるため、ループの実行回数は O(log(min(a, b))) です。最も時間のかかる入力は、701408733 と 433494437 のような連続するフィボナッチ数ですが、それでもわずか42ステップです。