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

この記事では、「指定した整数Xで割り切れる最小のK桁の数」を求める問題の解き方とアプローチについて詳しく解説します。

問題文

2つの整数 K（桁数）と X（割る数）が与えられます。Xで割り切れる最小のK桁の整数を求めてください。

アプローチ

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

1. まず、K桁の数のうち最小の値 MIN を求めます。MIN は「1の後に0が(K−1)個並ぶ数」、すなわち 10^K−1 です（例：K=5なら 10000）。
2. もし MIN を X で割った余りが 0 であれば、MIN がそのまま答えになります。
3. そうでない場合は、答えは (MIN + X) − ((MIN + X) % X) で計算できます。

この方法が成り立つ理由は、MIN から MIN + X までの範囲内に必ず X の倍数が1つ存在するためです。つまり、MIN + X を超えない最大の X の倍数を求めればよいことになります。

実装例

それでは、実際のコードを見てみましょう。

def answer(k, x):
    # K桁の数の最小値を計算
    min_num = pow(10, k - 1)
    if min_num % x == 0:
        return min_num
    else:
        # Xの倍数へ切り上げ
        return ((min_num + x) - ((min_num + x) % x))

x = 83   # 割る数
k = 5    # 桁数
print(answer(k, x))

出力

10043

処理の流れを確認

上記の例では、K = 5、X = 83 として実行しています。処理の流れを追ってみましょう。

• K桁の最小値 MIN は 10⁵⁻¹ = 10000
• 10000 ÷ 83 の余りは 40 なので 0 ではない → 手順3へ進む
• (10000 + 83) − (10083 % 83) = 10083 − 40 = 10043

実際に 10043 ÷ 83 = 121 となり、余りなく割り切れることが確認できます。また、10043 より小さい5桁の数で 83 で割り切れるものは存在しないため、これが正しい答えです。

別の書き方（ワンライナー）

Pythonでは、切り上げ除算のテクニックを使うと、同じ処理を1行で簡潔に書くこともできます。

x, k = 83, 5
print(((10 ** (k - 1) + x - 1) // x) * x)

こちらも同じ結果「10043」が出力されます。

まとめ

この記事では、Xで割り切れる最小のK桁の数を求めるアプローチについて学びました。ポイントは、「K桁の最小値 10^K−1 を基準にし、そこから最も近い X の倍数へ切り上げる」という考え方です。剰余演算を一度使うだけで答えが求まるため、計算量は O(1) と非常に効率的で、桁数や X が大きくなっても高速に動作します。