Description:
nをk個の異なる素数の和で表す方法は何通りあるか?(n <= 1120, k <= 14)
解は 2^31より小さい事が保障されている。
Answer:
(n+1)*(k+1)のサイズのテーブル、tblを用意し、tbl[0][0]だけ1, それ以外に0を入れておく。
このテーブルは、aを0以下のb個の異なる素数を用いて、tbl[a][b]通りに表せる、という意味を持つ。
このテーブルを一度舐める事で、aを2以下のb個の異なる素数を用いて、tbl[a][b]通りに表せる、というテーブルを作る事が出来る。
もう一度舐めると、aを3以下のb個の異なる素数 ... というテーブルを作る事が出来る。
5, 7, ..., 1117と全部の素数で繰り返すと、 aを1117以下のb個の異なる素数 ... というテーブルが出来る。
計算量は、 O((nまでの素数の数)* n * k)
1120までの素数は187個。
Source: