PythonでAの倍数かつ桁の合計がBと等しい最小の正の整数を求める方法

問題の概要

2つの整数 A と B が与えられたとき、「A で割り切れ、かつ各桁の数字の合計が B と等しい」という条件を満たす最小の正の整数 M を求めます。そのような数が存在しない場合は -1 を返します。

例えば、入力が A = 50、B = 2 の場合、出力は 200 となります。200 は 50 で割り切れ、桁の合計も 2 + 0 + 0 = 2 となり、両方の条件を満たす最小の数だからです。

解法のアプローチ：幅優先探索（BFS）

この問題は幅優先探索（BFS）を用いることで効率的に解けます。BFS は桁数の少ない数から順に探索を進めるため、最初に見つかった解が必ず最小値になります。

探索の状態は「現在の余り」と「これまでの桁の合計」のペアで管理します。ある数の余りが r のとき、その末尾に数字 i を付け加えると、新しい余りは (r × 10 + i) mod A として計算できます。この性質のおかげで、巨大な数を実際に構築しなくても余りの計算だけで済みます。

アルゴリズムの手順

• 余り a、桁の合計 b、および構築中の数字列（文字列）を保持する要素クラスを定義します
• キュー que を新しく作成します
• 初期状態 (0, 0, 空文字列) の要素を作成します
• visited[0][0] を 1 に設定し、要素をキューに追加します
• キューが空になるまで以下を繰り返します：
  • キューの先頭から要素を取り出します
  • 取り出した要素の a が 0 かつ b が目標値 B と等しい場合、その文字列を整数に変換して返します（答え発見）
  • i を 0 から 9 まで変えながら以下を処理します：
    • x := (temp_elem.a × 10 + i) mod A（新しい余り）
    • y := temp_elem.b + i（新しい桁の合計）
    • y ≤ B かつ visited[x][y] が未訪問の場合、visited[x][y] を 1 に更新し、新しい状態をキューに追加します
• キューが空になっても答えが見つからなければ -1 を返します

Pythonでの実装例

それでは、上記のアルゴリズムを実際に Python で実装してみましょう。

visited = [[0 for x in range(501)] for y in range(5001)]

class Element:
    def __init__(self, a, b, string):
        self.a = a
        self.b = b
        self.string = string

def get_number(a, b):
    que = []
    elem = Element(0, 0, "")
    visited[0][0] = 1
    que.append(elem)
    while len(que) > 0:
        temp_elem = que.pop(0)
        if temp_elem.a == 0 and temp_elem.b == b:
            return int(temp_elem.string)
        for i in range(0, 10):
            x = (temp_elem.a * 10 + i) % a
            y = temp_elem.b + i
            if y <= b and visited[x][y] == False:
                visited[x][y] = 1
                que.append(Element(x, y, temp_elem.string + str(i)))
    return -1

a, b = 50, 2
print(get_number(a, b))

実行結果

入力：

50, 2

出力：

200

まとめ

本記事では、「A の倍数かつ桁和が B と一致する最小の正の整数」を求める問題を、幅優先探索（BFS）で解く方法を紹介しました。余りと桁和を状態として管理することで、巨大な数を直接扱わずに済むのが最大のポイントです。計算量は状態数（余りの種類 × 桁和の範囲）に比例するため、制約が適度な範囲であれば高速に動作します。同様のテクニックは「特定の条件を満たす最小の数を求める」系の問題全般に応用できるので、ぜひ覚えておきましょう。