C++でxの倍数となる最大のk桁の数を求める方法

このチュートリアルでは、x で割り切れる最大の k 桁の数を求めるプログラムを C++ で実装する方法を解説します。

解き方の手順

この問題は、以下のシンプルな手順で解くことができます。

• 変数 x(割る数)と k(桁数)を初期化します。
• pow(10, k) - 1 を計算します。これは k 桁で表せる最大の数です(例:k = 3 なら 999)。
• 上記の値から x で割った余りを引きます。そうすることで、x で割り切れる最大の k 桁の数が求められます。

コード例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int answer(int x, int k) {
   int max = pow(10, k) - 1;
   return max - (max % x);
}
int main() {
   int x = 45, k = 7;
   cout << answer(x, k) << endl;
   return 0;
}

出力

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

9999990

仕組みの解説

このアルゴリズムがなぜ正しく動作するのかを簡単に説明します。pow(10, k) - 1 は k 桁で表現できる最大の数です。この数から x で割った余り(max % x)を引くと、結果は必ず x の倍数になります。また、余りを引いているため元の数より小さくなり、かつ k 桁の範囲内に収まります。したがって、「x で割り切れる最大の k 桁の数」という条件を満たすことになります。

計算量は O(1) であり、非常に効率的なアプローチです。

まとめ

本チュートリアルについて不明な点や質問がある場合は、コメント欄でお気軽にお知らせください。