https://www.acmicpc.net/problem/28263
以下の条件を全て満たす長さ $11$ の整数列 $p_1,p_2,\dots,p_{11}$ を一組見つけよ。
こんな簡潔な output only が Ruby V らしい。戦ってみよう。
前提知識: コルセルトの判定法
$n$ がカーマイケル数であることは、以下と同値である。
- $n$ の素因数 $p_i$ は全て奇数である。
- $n$ は square-free (重複した素因数を含まない) である。
- $n$ の全ての素因数 $p_i$ に対して、 $(n-1) \mod (p_i-1) = 0$ である。
問題の制約より上 $2$ つの条件は自明に満たされるので、 $3$ つ目の条件を吟味する。
この条件は以下のように言い換えられる。
- $(n-1) \mod \rm{lcm}$$(p_1-1,p_2-1,\dots) = 0$
ここで、この条件を「満たしやすい」ようにするには $\rm{lcm}$ を小さくすればよいという直感が働く。
ここで、 $p_i = k_i \times l + 1$ と生成することを考える。このとき、 $n-1$ は $l$ の倍数となる ( $n = \prod{p_i} = ml + 1$ ( $m $ は整数 ) ) ので言い換えた後の $\rm{mod}$ について $k_i$ の部分しか考えなくて良いことがわかる。
さらに、 $k_i$ を高度合成数 $X$ の約数の部分集合とすることを考える。このとき、十分多くの個数の $10^7 \le p_i < 10^8$ なる素数が生成できれば、 $\rm{mod}$ 部分が $Xl$ となるので、生成された素数の中から $11$ 個選んで条件を満たす確率が $1/X$ 程度だという大胆予想が立つ(仮に $1/X$ でなくともこれを大きく下回っていなければよい + 一組見つけよという問題なのでいったん信じる)。
この「十分多くの個数 $k$」であるが、 $C(k,11)$ がそこそこ大きければよく、例えば $k \ge 45$ 程度あれば $11$ 個の素数の選び方は $10^{10}$ 通り確保できる。
以上の流れは、次の二段階の探索を用いて実装できる。
- まず、素数を生成する式 $p_i = k_i \times l + 1$ の $l$ の部分を探索する。ある高度合成数 $X$ を固定した上で $l$ をいろいろ試して、より多くの $X$ の約数 $k_i$ について $10^7$ 以上 $10^8$ 未満の素数を生成するものを見つける。
- この結果、ある素数の集合 $P$ が得られる。
- 次に、サイズ $11$ の $P$ の部分集合を色々と探索する(乱択等でよい)。ここで得た集合に対してコルセルトの判定法を適用し、カーマイケル数を発見次第それを出力する。
試行錯誤の結果得たのが次のコード。確かにカーマイケル数を発見できている。
高度合成数や $l$ のとりかたがこれと違っても、マシンパワーでぶん回すなどすれば見つかると思います
お気持ちに素直に従えば解が見つかる構築問題、大好きっす…
