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

Xで割り切れる最小のK桁の数とは

「Xで割り切れる最小のK桁の数」を求める問題は、数式を活用したシンプルな方法で効率よく解くことができます。この手法は以下の手順で動作します。

解法のアルゴリズム

1. K桁の最小値（MIN）を計算する：例えば、K=2なら10、K=3なら100、K=4なら1000のように、10^K-1で求められます。
2. MINがXで割り切れるか確認する：割り切れる場合は、MINがそのまま答えになります。
3. 割り切れない場合：「(MIN + X) − ((MIN + X) % X)」という式で答えを導きます。

なぜこの式が機能するのか

MINがXで割り切れない場合、MIN以上でXの倍数となる最小の数を探す必要があります。「MIN + X」は確実にMINより大きい値なので、そこから剰余「(MIN + X) % X」を引くことで、Xの倍数へ切り下げられます。こうして得られるのが、MIN以上で最小のXの倍数、つまり答えとなります。

C++での実装例

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

int main() {
    int X = 83;
    int K = 5;

    // K桁の最小値を計算（例：K=5なら10000）
    int MIN = pow(10, K - 1);

    int answer;
    if (MIN % X == 0)
        answer = MIN;                          // 割り切れる場合はMINが答え
    else
        answer = (MIN + X) - ((MIN + X) % X);  // 割り切れない場合の式

    cout << X << " で割り切れる最小の " << K << " 桁の数は " << answer << endl;

    return 0;
}

出力結果

83 で割り切れる最小の 5 桁の数は 10043

実行結果の解説

この例では、X=83、K=5として実行しています。5桁の最小値である10000は83で割り切れないため、式「(10000 + 83) − ((10000 + 83) % 83)」を適用すると、答えとして10043が得られます。実際に10043 ÷ 83 = 121 となり、10043が83の倍数であることが確認できます。

まとめ

この方法の計算量はO(1)であり、ループで1つずつ候補を確認する方法と比べて格段に効率的です。KやXが大きくなっても高速に動作するため、競技プログラミングなどでも役立つ有用なテクニックといえます。