【Python】数字AとBのみで構成される数値がNを割り切れるかどうかを判定する方法

数値 n が与えられ、さらに2つの数値 a と b があるとします。このとき、「a と b のみを使って生成できる数値」の中に、n を割り切るものが存在するかどうかを判定する必要があります。

例えば、入力が n = 115、a = 3、b = 2 の場合、出力は True になります。これは、2と3だけで構成される数値「23」が 115 を割り切れる（115 ÷ 23 = 5）ためです。

解決のアプローチ

この問題は再帰的な探索によって解決できます。a と b を末尾に付け加えながら数値を伸ばしていき、その都度 n を割り切れるかを確認します。具体的な手順は以下の通りです。

1. 関数 util() を定義します。引数は temp、a、b、n です。
2. temp > n の場合、これ以上数値を伸ばしても意味がないため False を返します。
3. n が temp で割り切れる場合、条件を満たす数値が見つかったので True を返します。
4. それ以外の場合は、temp の末尾に a を追加した util(temp * 10 + a, a, b, n) と、末尾に b を追加した util(temp * 10 + b, a, b, n) を再帰的に呼び出し、少なくとも一方が True であれば True を返します。
5. メインの solve() 関数では、開始点として util(a, a, b, n) または util(b, a, b, n) を呼び出し、少なくとも一方が True であれば True を返します。

実装例

以下にPythonでの実装例を示します。

def util(temp, a, b, n):
    if temp > n:
        return False
    if n % temp == 0:
        return True
    return util(temp * 10 + a, a, b, n) or util(temp * 10 + b, a, b, n)

def solve(n, a, b):
    return util(a, a, b, n) or util(b, a, b, n)

n = 115
a = 3
b = 2
print(solve(n, a, b))

入力

115, 2, 3

出力

True

コードのポイント

• 枝刈り（pruning）：temp > n となった時点で探索を打ち切ることで、無駄な再帰呼び出しを防いでいます。
• 再帰による全探索：a と b を組み合わせて作れるすべての数値を効率的に網羅できます。
• 計算量：最悪の場合、桁数に対して指数的に増加しますが、枝刈りにより実際の探索範囲は大きく絞られます。

このように、シンプルな再帰処理を用いることで、「指定された数字だけで構成される約数が存在するか」という問題を簡潔に解決できます。