【競プロ】3個以上の整数の最大公約数と最小公倍数
ここでは、3個以上の整数の最大公約数や最小公倍数について見ていきます。競プロ 記事の一覧はこちら。
3個以上の整数の最大公約数
最大公約数と最小公倍数では、2つの整数の最大公約数や最小公倍数を見てきました。3個以上であっても、同じように最大公約数や最小公倍数を考えることができます。
例えば、 120, 156, 180 の最大公約数を考えてみましょう。3つの整数の場合でも、公約数は共通している約数のことです。例えば、1 や 2 は、3つの整数の共通の約数となっています。公約数を調べるために、約数を列挙していくのもいいのですが、なかなか大変です。
そこで、手動でやる場合は、素因数分解と最大公約数と最小公倍数で見た考え方を利用することが多いです。小さい素数から順番に割っていき、割れる個数の最小値を求めていく、という方法です。「こう書くのが標準」というものはないですが、次のように書くことが多いです。
\begin{array}{rll}
2 & ) \underline{\ 120 \quad 156 \quad 180} \\
2 & ) \underline{\ \ \ 60 \quad \ \ 78 \quad \ \ 90} \\
3 & ) \underline{\ \ \ 30 \quad \ \ 39 \quad \ \ 45} \\
& \quad 10 \quad \ \ 13 \quad \ \ 15 \\
\end{array}まず、3つの数字を並べて（1行目の右側）、小さい素数から順番に割り切れるかどうかを考えます。 $2$ で割り切れるので、左側に $2$ と書いて、その下に割った答えを書いていきます（2行目）。さらに、 $2$ で割り切れるので、もう一度左側に $2$ と書いて、その下に割った答えを書きます（3行目）。 $30$ がさらに $2$ で割れますが、他の2つが割れないので、次の素数に移ります。
次の素数 $3$ で割れるかを考えると、割れるので、同じように4行目を更新します。これ以上、すべてを割り切る素数はないので、ここでおしまいです。
こうして、共通で割れる素数と割れる回数を数えると、 $2$ で2回、 $3$ で1回だから、 $2^2\times 3=12$ が最大公約数だとわかります。
3個以上の整数の最大公約数を求めるコード
3個以上の整数の最大公約数を求めるために、先ほどの方法をコード上で行うことも可能です。つまり、素因数分解と最大公約数と最小公倍数で見たように、小さい素数からすべてを割り切る場合を調べていく、という方法です。この方法でもできるのですが、普通は、ユークリッドの互除法を応用することが多いです。
ユークリッドの互除法で見たように、a, b の最大公約数を求めるには、b, a % b の最大公約数を求めればいいのでした。繰り返していくと、余りはどんどん小さくなるので、最大公約数が求められる、という流れでした。では、3個以上の整数の場合はどうすればいいのでしょうか。
3個以上の場合を考えるために、先ほどの例を素因数分解して考えてみます。120, 156, 180 を素因数分解すると、次のようになります。
\begin{eqnarray}
120 &=& 2^3 & \times 3^1 & \times & 5^1 \\[5pt]
156 &=& 2^2 & \times 3^1 & & & \times & 13^1 \\[5pt]
180 &=& 2^2 & \times 3^2 & \times & 5^1 \\[5pt]
\end{eqnarray}約数は、もとの数の素因数だけの積であり、各指数ももとの数を超えないのでした（参考：素因数分解と約数と倍数）。なので、この3個の整数の公約数は、どの整数にも共通に存在する素因数だけの積であり、指数はもとの数を超えません。このことから、最大公約数は、 $2$ を2回、 $3$ を1回掛けたものになることがわかります。 $5, 13$ はすべてに含まれているわけではないですし、 $2^3$ や $3^2$ だともとの数の指数より大きくなってしまうケースがあるので、こういう場合は公約数にはなりません。
結局、3個以上であっても、素因数分解をして、各素因数の指数の一番小さいものを集めてくればいいことがわかります。これを小さい問題に分割してみます。まず「120と156の最大公約数」を求めてから、「これと180との最大公約数」を求めます。一度に全体をターゲットにするのではなく、順番に処理をしていくわけです。
各素因数の指数について、全体を見渡してから一番小さいものを選んでも、前から2つずつ見ていって小さい方を選んでいっても、最終的には一番小さいものが得られます。このように考えることで、3個以上の場合は、2個の場合を繰り返して求められるため、2個の場合に帰着されます。C++では、次のようなコードで求められます（参考：ユークリッドの互除法）。
#include <iostream>
using namespace std;
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
int main() {
int n, a, b;
cin >> n >> a;
for (int i = 1; i < n; i++) {
cin >> b;
a = gcd(a, b);
}
cout << a;
return 0;
}整数の個数 n と、n 個の整数を入力すると、最大公約数が返ってきます。先ほどの例であれば、3 120 156 180 という入力に対応します。まず、 a に 120 を入れ、a, 156 の最大公約数を a に入れ直し、a, 180 の最大公約数を a に入れています。こうして、前から順番に最大公約数を求めて、それを a に格納する、というのを繰り返して最大公約数を求めています。
上の gcd は再帰関数を用いていますが、2つの整数の最大公約数を求められるなら他のかき方でも構いません。
だいぶ難しいですが、AtCoder ABC 125 C - GCD on Blackboard に挑戦できるかもしれません。計算量を、減らすための工夫も必要なので、最大公約数が求められるだけではダメですが、考えてみましょう。
3個以上の整数の最小公倍数
3個以上の整数であっても、最小公倍数は共通の公倍数の中で一番小さいもの、ということです。この求め方を考えてみます。
素因数分解と最大公約数と最小公倍数では、正の整数 $a,b$ の最大公約数と最小公倍数との積が $ab$ と一致することを見ました。しかし、これは3個以上の場合では成り立ちません。例えば、 $2,3,4$ の最大公約数は $1$ で最小公倍数は $12$ ですが、3個の整数の積にはなっていません。
そのため、まずは素因数分解を使った形で考えてみます。
\begin{eqnarray}
120 &=& 2^3 & \times 3^1 & \times & 5^1 \\[5pt]
156 &=& 2^2 & \times 3^1 & & & \times & 13^1 \\[5pt]
180 &=& 2^2 & \times 3^2 & \times & 5^1 \\[5pt]
\end{eqnarray}最小公倍数は、上の素因数分解に出てくる素数をすべて集め、各素因数の指数は一番大きいものを選んだものになります。つまり、上の3つの整数の最小公倍数であれば\[ 2^3\times 3^2\times 5^1\times 13^1=4680 \]になる、ということです。
この場合も、最大公約数のときと同じように、全体の中で一番大きいものを選ぶことは、前から2個ずつ比較して大きい方を選んだ結果と同じになることがわかります。例えば、素因数 $3$ であれば、120, 156 を比較するとどちらも指数は $1$ ですが、 180 の場合は $2$ なので、最終的に最大値 $2$ が得られます。
つまり、最小公倍数の場合も、整数がたくさんある場合は、初めから順番に最小公倍数を求めていけばいいことがわかります。「「120と156の最小公倍数」と180の最小公倍数」が、3つの整数の最小公倍数になる、ということです。C++のコードで書けば、次のようになります。
#include <iostream>
using namespace std;
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int main() {
int n, a, b;
cin >> n >> a;
for (int i = 1; i < n; i++) {
cin >> b;
a = lcm(a, b);
}
cout << a;
return 0;
}最小公倍数を更新して a に代入していっています。3 120 156 180 と入力してみると、4680 という正しい答えが返ってきます。
おわりに
ここでは、3個以上の整数に対して、最大公約数や最小公倍数を求める方法を見てきました。2個の場合に帰着させると考えやすくなります。このように、競プロの問題では、小さい問題に分割する方法がいろいろな形で出題されます。
