Xで割り切れる最大のK桁の数を求めるC++プログラム

2つの整数 X と K が与えられます。ここで K は桁数を表します。この問題の目的は、Xで割り切れる最大のK桁の数を見つけることです。

入力：X = 30, K = 3
出力：980

考え方

出力例の 980 は、30で割り切れる最大の3桁の数です。

この問題は次の手順で解くことができます。

1. まず、10 の K 乗から 1 を引くことで、K桁の数の最大値（MAX）を求めます。
   例：K = 3 の場合、10³ − 1 = 999
2. 次に、MAX を X で割った余り（MAX % X）を MAX から引きます。
   これにより、Xで割り切れる最大のK桁の数が得られます。

余りを引くという操作により、MAX 以下でかつ X の倍数である最大の数に必ず到達できるため、追加のループ処理は不要です。

サンプルコード

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int X = 20;
    int K = 3;
    // K桁の最大の数を求める（例：K=3 なら 999）
    int MAX = pow(10, K) - 1;
    // 余りを引いて、Xで割り切れる最大のK桁の数を出力
    cout << (MAX - (MAX % X));
}

実行結果

980

コードの解説

• pow(10, K) - 1 によって、K桁で表せる最大の数（999 など）を計算します。
• MAX % X は、MAX を X で割ったときの余りです。
• この余りを引けば、結果は必ず X の倍数になり、かつ K桁の範囲内で最大の値となります。

このアルゴリズムの計算量は O(1) であり、非常に効率的です。大きな桁数や大きな X の値に対しても高速に動作します。