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

この問題では、Xで割り切れる最小のK桁の数を求めます。まず、数式 10^(k-1) を使ってK桁の最小の数を求め、その数がXで割り切れるかどうかを確認します。割り切れない場合は、次の数式を使って正確な答えを導き出します。

(min + X) − ((min + X) mod X)

具体例として、「29で割り切れる5桁の数」を求めてみましょう。5桁の最小の数は10000ですが、これは29で割り切れません。そこで上記の数式を適用すると、次のようになります。

(10000 + 29) − ((10000 + 29) mod 29) = 10029 − 24 = 10005

求められた数10005は、実際に29で割り切れることが確認できます。

アルゴリズム

minKDigit(k, x)

begin
    min = 10 ^ (k-1)
    if min is divisible by x, return min
    otherwise return (min + x) – ((min + x) mod x)
end

アルゴリズムの流れは以下の通りです。

1. K桁の最小の数 min を 10^(k-1) として計算します。
2. min が x で割り切れる場合は、min をそのまま返します。
3. 割り切れない場合は、(min + x) − ((min + x) mod x) を計算して返します。この式により、min 以上で x で割り切れる最小の数が得られます。

実装例

#include<iostream>
#include<cmath>
using namespace std;
long min_k_digit(int k, int x) {
    // K桁の最小の数を取得
    int min = pow(10, k-1);
    if(min % x == 0) {
        return min;
    }
    return (min + x) - ((min + x) % x);
}
main() {
    int k, x;
    cout << "Enter Digit Count(K) and Divisor(N): ";
    cin >> k >> x;
    cout << "Result is: " << min_k_digit(k, x);
}

このプログラムでは、まず pow(10, k-1) によってK桁の最小の数を取得します。その数がXで割り切れる場合はそのまま返し、割り切れない場合は剰余演算（%）を使って、条件を満たす最小の数を計算して返します。

出力例

Enter Digit Count(K) and Divisor(N): 5 29
Result is: 10005

5桁の数で29の倍数となる最小の数として、10005が出力されました。

出力例（別のケース）

Enter Digit Count(K) and Divisor(N): 6 87
Result is: 100050

同様に、6桁の数で87の倍数となる最小の数は100050となります。

まとめ

この手法のポイントは、K桁の最小の数から出発し、剰余演算を一度だけ行うことで目的の数を求められる点です。ループで一つずつ数を確認していく方法と比べ、計算量がO(1)で済むため、非常に効率的なアプローチといえます。