階乗 N! を素因数分解して得られる素因数の数を P(N) とすると、P(N) に対応する最小の N を求めて欲しいのが ACM #10856 Recover Factorial という問題。

例: 4! = 4*3*2*1 = 2*2*3*2 ⇒ P(4) = 4
   6! = 6*5*4*3*2*1 = 3*2*5*2*2*3*2 ⇒ P(6) = 7
   10! = 10*9*8*7*6*5*4*3*2*1 = 2*5*3*3*2*2*2*7*2*3*5*2*2*3*2
     ⇒ P(10) = 15

N と P(N) との対応関係は最初のところでは以下の通り。
   N  0 1 2 3 4 5 6 7  8  9  10 …
  P(N) 0 0 1 2 4 5 7 8 11 13 15 …

注意して欲しいのは、P(N) の値は連続しておらず、3, 6, 9, 10, 12 等にはならないこと。また、問題の入力データは、0 <= P(N) <= 10000001 の範囲内であること。

さて、試行錯誤の末、つぎの解き方にたどり着いた。

 (1) 1 ~ 2703663 までの N を素因数分解し、それぞれの素因数の数を 配列 F[1..N] に格納する。(素数のエラトステネスのふるいを活用。)
 (2) (1)で求まった F配列 を累計して、P(N) に関するテーブルを作成する。漸近式: P[N] = P[N-1] + F[N]、P[0] = 0。
 (3) バイナリサーチで、入力値として指定された P(N) を (2)のテーブルから探し出す。

(1)のところの値 2703663 は、最大のP[N] = 10000001時のN である。また、素数のエラトステネスのふるいを活用するところは、自分なりの工夫を多少したつもりだが、全体的に素直な解き方だろう。しかも、計算結果は満足のいく 0.455 秒、現時点ではベスト1を記録

参考のため、C言語プログラムを載せておく。エラトステネスのふるい(の変形)と、バイナリサーチの部分は、多少ためになるかもしれないと思ってるので。
p10856.c

Comments are closed.

Post Navigation