ABC475 D - Alphametic Prime

文字素数

考え方

いわゆる覆面算のようにして、素数にできるかという問題。
$S$ が $7$ 文字以下なので、対応する素数として出てくるものは、$10000000$ 未満のもののみ。
$S$ の文字数がもっと短ければ、上限はもっと小さくなる。

ということで、エラトステネスの篩で、$10^{|S|}$ 未満の素数を全て列挙すればよい。
$|S|$ 桁の素数を全て文字化し、「同じ文字がどの位置にあるか」を判定する関数にかける。
与えられた文字列と同じ結果になったものがあれば、それを答えればよい。

計算量は素数列挙部分が支配的で $O(10^{|S|}\log |S|)$ である。

入力を受け取る。

s: "motor"

motor では、o が $2$ 文字目と $4$ 文字目に現れる。
それ以外の m, t, r はそれぞれ $1$ 回ずつ現れ、互いに異なる文字である。

まず、エラトステネスの篩で $100000$ 未満の素数を列挙する。
そのうち $5$ 桁の素数を順に文字列へ変換し、同じ文字が現れる位置を motor と比較していく。

例えば 10007 では、0 が $2$ 文字目から $4$ 文字目までの $3$ か所に現れるので、motor とは一致しない。
その後の素数についても同様に調べていく。

10607 では、0 が $2$ 文字目と $4$ 文字目に現れる。
それ以外の 1, 6, 7 はそれぞれ $1$ 回ずつ現れ、互いに異なる数字である。
したがって、同じ文字が現れる位置が motor と一致する。

よって、10607 を答えとして出力する。

特になし。

特になし。