【競プロ】最大公約数と最小公倍数

🕒 2019/10/22 🔄 2023/05/01

ここでは、最大公約数と最小公倍数について見ていきます。これらも、整数の問題ではよく登場します。競プロ記事の一覧はこちら。

📘 目次

公倍数と公約数

$3$ の倍数には、 $3,6,9,12,\cdots$ があり、 $4$ の倍数には、 $4,8,12,16,\cdots$ があります。 $12$ はどちらにも含まれています。このように、2つの整数 $a,b$ について、 $a$ の倍数になっていて $b$ の倍数にもなっているものを、 $a,b$ の公倍数(common multiple) といいます。 $3,4$ の公倍数は、 $12$ 以外にも、 $24$, $36$ など、無数にあります。

ある整数 $c$ が、2つの整数 $a,b$ の公倍数であるかどうかは、 $c$ を $a,b$ で割ったときの余りがどちらも $0$ であるかどうかを確認すればいいので、コードで書くと次のようになります。

#include <iostream>
using namespace std;

int main() {
  int a = 3, b = 5, c = 15;
  if (c % a == 0 && c % b == 0) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  return 0;
}

約数に対しても同じようなものを考えられます。 $12$ と $16$ の約数を考えると、 $4$ や $1$ などが共通しています。このように、2つの整数 $a,b$ について、 $a$ の約数になっていて $b$ の約数にもなっているものを、 $a,b$ の公約数(common divisor) といいます。

次のコードは、正の整数 $a,b$ に対して、公約数を小さい方から順番に書いていくものです。

#include <iostream>
using namespace std;

int main() {
  int a = 12, b = 16;
  for (int i = 1; i <= a; i++) {
    if (a % i == 0 && b % i == 0) {
      cout << i << " ";
    }
  }
  return 0;
}

最大公約数

公約数のうち、最大のものを最大公約数(greatest common divisor) といいます。最大公約数は整数に関連する問題で登場することが多く（競プロでも数学でも）、アルファベットの頭文字をとって、GCD と略されることもあります。

次のコードは、正の整数 $a,b$ の最大公約数を、愚直に求めるコードです。順番に割り算をしてみて、割り切れるものを探し、その中で最大のものを計算しています。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);

  int ans = 1;
  for (int i = 1; i <= sqrt(a); i++) {
    if (a % i == 0) {
      int j = a / i;
      if (b % i == 0) ans = max(ans, i);
      if (b % j == 0) ans = max(ans, j);
    }
  }
  
  cout << ans;
  return 0;
}

約数は自分自身より大きくなることはない（例えば、 $36$ の約数が $36$ より大きくなることはない）ので、min(a, b)までの数を調べればいいです。上のコードでは、 a が b 以下となるように、はじめに swap をしています。

a の約数を見つけるには、 sqrt(a) 以下の整数を調べればいいです（参考：倍数と約数、素因数分解）。 $a$ 個の丸を縦に $i$ 個並べるとき、 $j$ 列ピッタリに並べられたら、 $i,j$ は約数であることがわかるので、これらが $b$ の約数になっているかどうかを調べます。

競プロでは、最大公約数を探すときには、上の方法よりももっと効率のいい方法がよく使われますが、それは別の機会に見ることにします。

上のコードでほとんどできていますが、AOJ ALDS1_1_B Greatest Common Divisorに挑戦できるでしょう。上のコードは想定解ではないので、現時点ではヒントは気にしないでおきましょう。

互いに素

どんな整数でも $1$ は約数になるので、 $1$ は必ず公約数になります。そのため、最大公約数は少なくとも $1$ です。

一方、2つの正の整数 $a,b$ の最大公約数が $1$ のとき、 $a$ と $b$ は互いに素(coprime) といいます。例えば、 $2$ と $5$ は互いに素です。 $12$ と $77$ も互いに素です。「互いに素」は「素数」と同じ「素」という漢字を使っていますが、別に素数でなくても「互いに素」になることはあります。

互いに素かどうかを調べるには、最大公約数が $1$ であるかどうかを調べればよく、先ほどのコードが使いまわせるでしょう。

「互いに素」は数学的には重要な概念で、これから何度も登場します。

最小公倍数

公倍数のうち、正の整数で最小のものを最小公倍数(least common multiple) といいます。頭文字をとって、LCM と略されます。公倍数は無数にありますが、最小公倍数は一つだけです。

LCM と GCD のどちらがどちらを表しているかが紛らわしいですが、L が least（最小）の略で、G が greatest（最大）の略だということを頼りに思い出しましょう。

最大公約数とは異なり、最小公倍数のほうはどこまで調べればいいか、少しわかりにくいです。しかし、これも限界値はあります。

$a,b$ の両方の倍数になっているもののうち、すぐに見つけられるものは $ab$ です。これより大きいものが最小公倍数になることはありません。そのため、これ以下の数で、 $a,b$ で割ったときに割り切れるかどうかを調べていけば、最小公倍数を見つけられます。もう少し効率的にやるなら、 $b$ から $ab$ までの $b$ の倍数の中で、 $a$ で割り切れるものを小さい方から順番に調べていきます。

愚直に調べていくなら、次のようなコードになります。

#include <iostream>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);

  for (int i = 1; i <= a; i++) {
    if (b * i % a == 0) {
      cout << b * i;
      return 0;
    }
  }
  return 0;
}

最小公倍数の見つけ方も、効率のいい方法がありますが、これも別の機会に見ることにしましょう。