C++で3つの指定した数値すべてで割り切れる最大のN桁の数を求める方法

はじめに

このチュートリアルでは、指定された3つの数値すべてで割り切れる、N桁の最大の数を求めるプログラムをC++で作成します。

一見すると総当たりで調べたくなりますが、最小公倍数(LCM)を利用することで、効率的に答えを導き出せます。その考え方と実装方法を順番に見ていきましょう。

解決手順

問題を解くための手順は以下の通りです。

• 3つの数値と桁数nを初期化します。
• 3つの数値の最小公倍数(LCM)を求めます。
• N桁の最大の数(999...9)を求めて保存します。
• その最大の数がLCMで割り切れる場合は、そのまま答えとして返します。
• 割り切れない場合は、最大の数から剰余を引いた数を答えとして返します。

なぜLCMを使うのか

ある数が3つの数値すべてで割り切れるためには、その数が3つの数値の最小公倍数の倍数である必要があります。つまり、「N桁の最大の数」以下で最大の「LCMの倍数」を探せばよいことになります。具体的には、N桁の最大の数をLCMで割った余りを引けば、条件を満たす最大の数が求まります。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int LCM(int x, int y, int z) {
   int ans = ((x * y) / (__gcd(x, y)));
   return ((z * ans) / (__gcd(ans, z)));
}
int findNumber(int n, int x, int y, int z) {
   int lcm = LCM(x, y, z);
   int largestNDigitNumber = pow(10, n) - 1;
   int remainder = largestNDigitNumber % lcm;
   if (remainder == 0) {
      return largestNDigitNumber;
   }
   largestNDigitNumber -= remainder;
   if (largestNDigitNumber >= pow(10, n - 1)) {
      return largestNDigitNumber;
   }
   return 0;
}
int main() {
   int n = 4, x = 6, y = 7, z = 8;
   int result = findNumber(n, x, y, z);
   if (result != 0) {
      cout << result << endl;
   }else {
      cout << "Not possible" << endl;
   }
   return 0;
}

コードのポイント

• LCM関数: 2つの数の最小公倍数を「積 ÷ 最大公約数」で求め、それを3つ目の数にも適用することで、3つの数のLCMを計算しています。
• findNumber関数: N桁の最大の数は「10ⁿ − 1」で表されます。これをLCMで割った余りを引き算することで、条件を満たす最大の数を求めています。
• 存在チェック: 余りを引いた結果がN桁未満になる場合(例： 桁数に対してLCMが大きすぎる場合)は、条件を満たす数が存在しないため0を返します。

実行結果

上記のコードを実行すると、次の出力が得られます。

9912

4桁の最大の数9999を、6・7・8の最小公倍数168で割ると余り87が出るため、9999 − 87 = 9912が答えとなります。実際に9912は6でも7でも8でも割り切れることが確認できます。

まとめ

今回は、3つの指定された数値すべてで割り切れる最大のN桁の数を、最小公倍数を活用して効率的に求める方法を紹介しました。総当たりではなく数学的な性質を利用することで、計算量を大幅に抑えられるのがポイントです。

チュートリアルについて質問がある場合は、ぜひコメント欄でお知らせください。