【競プロ】素因数分解と最大公約数と最小公倍数

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

ここでは、素因数分解を使って、最大公約数や最小公倍数を求める方法を見ていきます。また、最大公約数と最小公倍数の積に関する性質も見ていきます。競プロ記事の一覧はこちら。

📘 目次

最大公約数と素因数分解

公約数や最大公約数を求めるときにも、素因数分解を利用することができます。素因数分解と約数と倍数で見た約数の考えを応用していきます。

2つの正の整数 $A, B$ があったとします。この2つの素因数をすべて集めて $p_1,p_2,\cdots, p_n$ とおき、
\begin{eqnarray} A &=& p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} \\[5pt] B &=& p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n} \\[5pt] \end{eqnarray}と表します。なお、 $a_i, b_i$ は0以上の整数で、どちらも0のケースはないとします。このとき、公約数や最大公約数を素因数分解したときにどうなるか考えてみましょう。

まずは公約数について考えます。素因数分解と約数と倍数で見た約数のときと同じように考えると、どちらの約数にもなっていることから、他の素因数が含まれてないことがわかります。また、 $p_i$ の指数が $a_i,b_i$ よりも大きいこともありません。このことから、公約数は、\[ p_1^{d_1}p_2^{d_2}\cdots p_n^{d_n} \]と書けます。ここで、各 $d_i$ は、0以上で、 $\min (a_i,b_i)$ 以下の整数です。

また、これらの公約数の中で一番大きいものは、各 $d_i$ が一番大きくなるようにとったときなので、 $p_i$ の指数が $\min (a_i,b_i)$ となっているとき、だとわかります。

例えば、 $2\cdot 3^3\cdot 7^2$ と $2^3\cdot 5\cdot 7^2$ (2646 と 1960) の最大公約数であれば、各素因数の小さい方をとっていって、\[ 2^1\cdot 3^0\cdot 5^0 \cdot 7^2= 98 \]と求められます。素因数分解した後の形がわかっていれば、最大公約数を求めることは簡単ですね。

このことを踏まえると、素因数分解を利用して最大公約数を求めると次のようになります。

#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 = 2; i <= sqrt(a); i++) {
    while (a % i == 0 && b % i == 0) {
      ans *= i;
      a /= i;
      b /= i;
    }
    while (a % i == 0) a /= i;
    while (b % i == 0) b /= i;
    if (a == 1 || b == 1) break;
  }
  if (b % a == 0) ans *= a;
  
  cout << ans;
  return 0;
}

sqrt(a) 以下の素因数に対して、両方ともを割り切る回数を数えています。最後に、 a に素数が残るケースを考慮しています（参考：素因数分解）。こうして最大公約数を求めることもできます。

この内容を踏まえれば、AOJ ALDS1_1_B Greatest Common Divisor を別のコードで通せるようになるでしょう。

最小公倍数と素因数分解

公倍数や最小公倍数についても、素因数分解を利用して求めてみましょう。

先ほどと同じように、2つの正の整数 $A, B$ があって、同じように素因数分解したとします。このとき、公倍数や最小公倍数を素因数分解したときにどうなるか考えてみましょう。

公倍数は公約数のときの逆です。どちらの倍数にもなっていないといけないので、 $p_i$ の指数は $a_i$ 以上であり、 $b_i$ 以上でもある必要があります。また、他の素因数を含めたものも倍数となります。

また、公倍数の中で一番小さいものは、 $p_1$ ～ $p_n$ 以外の素因数を含まず、各 $p_i$ の指数が一番小さくなるようにとったときなので、 $\max (a_i,b_i)$ となっているときだとわかります。

このように、素因数分解をして、各素因数の指数を見ることで、最小公倍数も求めやすくなります。

コードでも、最大公約数のときと同じように書いてもいいのですが、次で見るように、最小公倍数は最大公約数を使ってもう少し簡単に求めることができます。

最大公約数と最小公倍数との積

ここまで見た内容をまとめてみます。2つの正の整数 $A, B$ があったとします。この2つの素因数をすべて集めて $p_1,p_2,\cdots, p_n$ とおき、
\begin{eqnarray} A &=& p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} \\[5pt] B &=& p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n} \\[5pt] \end{eqnarray}と表します。なお、 $a_i, b_i$ は0以上の整数で、どちらも0のケースはないとします。

最小公倍数を $C$ とし、最大公約数を $D$ とすると、素因数分解したときに出てくる素因数は、同じく $p_1,p_2,\cdots, p_n$ となるのでした。なので、各指数を $c_i$, $d_i$ とすると、
\begin{eqnarray} C &=& p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n} \\[5pt] D &=& p_1^{d_1}p_2^{d_2}\cdots p_n^{d_n} \\[5pt] \end{eqnarray}となります。ここで、 $c_i$ は $\max (a_i,b_i)$ であり、 $d_i$ は $\min (a_i,b_i)$ です。

ということは、 $c_i$ と $d_i$ は、どちらかが $a_i$ で、もう片方は $b_i$ となっているはずです。なので、\[ a_i+b_i=c_i+d_i \]が成り立ちます。

これを利用して、元の2つの数 $A, B$ の積と、最小公倍数 $C$ と最大公約数 $D$ との積を考えてみます。 $p_i$ の指数は、前者は $a_i+b_i$ で、後者は $c_i+d_i$ となり、一致することがわかります。式で書くと、
\begin{eqnarray} AB &=& p_1^{a_1+b_1}p_2^{a_2+b_2}\cdots p_n^{a_n+b_n} \\[5pt] CD &=& p_1^{c_1+d_1}p_2^{c_2+d_2}\cdots p_n^{c_n+d_n} \\[5pt] \end{eqnarray}となり、右辺同士が等しいことから、\[ AB=CD \]だとわかります。

具体的な数を使って、計算してみましょう。例えば、 $56$ と $70$ の最小公倍数を考えるとします。公倍数を調べるには、大きな数を扱わねばならず、少し面倒です。それに比べると、最大公約数はまだ考えやすいです。試行錯誤すると $14$ だとわかります。これがわかれば、上で見た内容から、最小公倍数は\[ 56\times 70 \div 14=56\times 5=280 \]だとわかる、ということです。倍数を列挙していくより楽なことがわかります。

もとの2つの整数の積は簡単に求められます。最大公約数は先ほどのコードを使いまわすとすると、 $AB=CD$ となることを利用して最小公倍数を求めるには、次のようなコードでできます。

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

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

  int lcm = a * b;
  int gcd = 1;
  for (int i = 2; i <= sqrt(a); i++) {
    while (a % i == 0 && b % i == 0) {
      gcd *= i;
      a /= i;
      b /= i;
    }
    while (a % i == 0) a /= i;
    while (b % i == 0) b /= i;
    if (a == 1 || b == 1) break;
  }
  if (b % a == 0) gcd *= a;
  
  lcm /= gcd;
  cout << lcm;
  return 0;
}

最小公倍数を求めるには、最大公約数を求めればOKです。最大公約数をもっと楽に求める方法を今後学ぶので、それを見た後は、最小公倍数を求めるのもかなり楽になります。