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

この記事では、「Xで割り切れる最大のK桁の整数」を求める問題をC++で解く方法を解説します。一見すると複雑そうに思えますが、実は非常にシンプルな数式だけで答えを導き出せる、アルゴリズム学習に最適な題材です。

解法の基本的な考え方

K桁の最大の整数は、次の公式で簡単に求められます。

max = 10^k − 1

例えば5桁なら「99999」、6桁なら「999999」となります。この最大値がそのままXで割り切れれば、それが答えです。もし割り切れない場合は、次の式を使うことで、Xで割り切れる最大のK桁の数を一発で計算できます。

max − (max mod X)

具体例：5桁かつ29の倍数となる最大の数

まず、5桁の最大値である「99999」を考えます。しかし、99999は29では割り切れません（99999 ÷ 29 の余りは7）。そこで上記の公式を適用すると、

99999 − (99999 mod 29) = 99999 − 7 = 99992

となり、答えは「99992」です。実際に99992は29で割り切れることが確認できます。

アルゴリズム

maxKDigit(k, x)

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

処理の流れは以下の通りです。

1. 10^k − 1 を計算し、K桁の最大値 max を求める
2. max が X で割り切れる場合は、そのまま max を返す
3. 割り切れない場合は、max から「max を X で割った余り」を引いた値を返す

C++による実装例

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

long max_k_digit(int k, int x){
    // K桁の最大値を取得
    int max = pow(10, k) - 1;
    if(max % x == 0){
        return max;
    }
    return (max) - (max % x);
}

main() {
    int k, x;
    cout << "Enter Digit Count(K) and Divisor(N): ";
    cin >> k >> x;
    cout << "Result is: " << max_k_digit(k, x);
}

このコードでは、pow(10, k) - 1 でK桁の最大値を計算し、剰余演算子 % を使って余りを差し引いています。計算量はO(1)であり、非常に効率的です。

実行結果

例1：5桁・29の場合

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

例2：6桁・87の場合

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

まとめ

Xで割り切れる最大のK桁の数は、「K桁の最大値（10^k − 1）から、それをXで割った余りを引く」というシンプルな式で求められます。ループで一つずつ確認する方法と比べて計算量が大幅に少なく、競技プログラミングや数学的思考のトレーニングにも役立つテクニックです。ぜひ自分のコードでも活用してみてください。