Pythonで0と9のみで構成されるnの最小倍数を見つけるプログラム

問題概要

整数 n が与えられたとき、「0」と「9」の2種類の数字だけで構成され、かつ n の倍数となる最小の正整数 x を求めることを考えます。

例えば、入力が n = 26 の場合、出力は 90090 となります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• m を 9 に初期化する
• x を 1 に初期化する
• m が n で割り切れない間、以下を繰り返す
  • x を 1 増やす
  • x の2進数表現に含まれるすべての「1」を「9」に置き換えた数を m とする
• m を整数として返す

この方法のポイントは、0と9のみで構成される数は、2進数の「0」と「1」で構成される数と同じ形をしているという点です。つまり、x を順に増やしながらその2進数表現の「1」を「9」へ置き換えることで、候補となる数を効率的に生成できます。

実装例

以下のPythonコードで、実際の実装を確認してみましょう。

def solve(n):
    m = 9
    x = 1
    while m % n != 0:
        x += 1
        m = int(bin(x)[2:].replace('1','9'))
    return m

n = 26
print(solve(n))

入力

26

出力

90090

コードの解説

bin(x) 関数は整数 x を2進数の文字列（先頭に "0b" が付く）に変換します。[2:] スライスで "0b" を取り除き、replace('1','9') によって「1」をすべて「9」に置き換えた後、int() で整数へ変換しています。これにより、0と9のみで構成される数を小さい順に生成し、n で割り切れる最初の数を見つけ出すことができます。