🙆

AtCoder ユークリッドの互除法の計算量

2023/05/06に公開

C++

ABC297のD問題を解きながら、ユークリッドの互除法の計算量について考察します。
コンテストサイト:
https://atcoder.jp/contests/abc297
D - Count Subtractions

問題概要

正整数 A,B が与えられます。
A=B になるまで以下の操作を繰り返します。
A,B の大小関係に応じて、次のどちらかの処理を行う。
A>B ならば、A を A−B で置き換える。
A<B ならば、B を B−A で置き換える。
A=B になるまで、操作を何回行うか求めてください。

問題リンク:

解法

問題文の操作をそのまま実装すると

この問題文の操作は、ユークリッドの互除法と呼ばれています。
ユークリッドの互除法とは、2つの正の整数の最大公約数を求める方法です。
最大公約数とは、2つの数を割り切ることができる最大の数です。
以下のような手順で最大公約数を求める方法です。

2つの自然数a,b(a≧b)を用意する。
aをbで割った余りをrとする。
rが0ならば、bが最大公約数である。
rが0でなければ、aにbを代入し、bにrを代入し、2に戻る。

ユークリッドの互除法の置き換える操作の回数を求めるのが今回の問題です。

C++で問題文の操作のコードを書くと、以下のようになります。

C++

#include <iostream>
using namespace std;

// ユークリッドの互除法を実装する関数
int euclid(int a, int b) {
    // 操作の回数をカウントする変数
    int count = 0;
    // AとBが等しくなるまで繰り返す
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
        count++;
    }
    // 操作の回数を返す
    return count;
}

int main() {
    int a, b;
    cin >> a >> b;
    // ユークリッドの互除法を呼び出して、答えを出力する
    cout << euclid(a, b) << endl;
    return 0;
}

これで、実装できましたが、
Aが大きく、Bが小さい数だと実行制限時間をオーバーしてしまい
TLEエラーになってしまいます。

工夫して実装しよう

ここで、工夫して実装してみます。
公式の解説以上の実装を思い浮かばなかったので公式のコードを実装例を読み解いていきます。

まず、始めに A>BでもA<Bでもやる操作は変わらないので、
AがBより小さければA>Bとなるように入れ替えます。

B=0 になるまで以下を繰り返します。

答えにAをBで割った商を足す。
AをAmodBで置き換える。
A,Bを入れ替える。

最後に、答えから1を引きます。

元の操作での
A,B の大小関係が同じ時の操作を一度にまとめて行うだけなので、
上記で答えは正しく求まります。
最後に1を引くのは、A=Bとなったときに余分に1回操作してしまうためです。

C++

#include<iostream>
using namespace std;
int main() {
  long long a,b;
  cin>>a>>b;
  long long ans=0; // 操作回数を0に初期化
  if(a<b) swap(a,b); // aがbより大きくなるように入れ替える
  while(b>0){
    ans+=a/b; // 操作回数にaをbで割った商を足す
    a%=b; // aにaをbで割った余りを代入する
    swap(a,b); // aとbを入れ替える
  }
  cout<<ans-1<<endl; // 余分に足した分を引く
  return 0;
}

ユークリッドの互除法の計算量

AをAmodBで置き換えると、Aが元の半分未満になります。

証明

AとBは自然数で、A>Bであるとします。
AmodBとは、AをBで割ったときの余りなので、
AmodB=A-B*(A/B)=A*(1-B/(A/B))と書けます。ここで(A/B)は商を表します。
この式から、AmodBがAの半分未満になるためには、
1-B/(A/B)<1/2であればよいことがわかります。
これを変形すると、B/(A/B)>1/2となります。
さらに変形すると、(A/B)^2<2Bとなります。
この不等式は、A≤Bであることから必ず成り立ちます。
なぜなら、(A/B)^2≤1<2Bであるからです。
よって、AmodB<A/2であることが証明されました。
Q.E.D.

従って、ユークリッドの互除法のAをAmodBで置き換えるステップを2回繰り返して、
A、Bはそれぞれ半分以下になります。
よって、ざっくりと2log(min(A,B))回のステップを踏むことになります。
今回の問題のアルゴリズムの計算量は O(log(min(A,B))) です。
これは、AとBを交換しながら剰余を求めていくため、
AとBの小さい方に対してlogのオーダーで計算回数が増加することを意味します。