SRM388 Div2 1000

問題

k-smoothな正の整数とは、その最大の素因数がkを超えないような整数をいう。
N以下の正の整数のうちでk-smoothな整数の個数を返す。

考え方

やるだけ。
■素数の組み合わせで求める方法
1000以下の素数について、各素数同士の組み合わせでできるN以下の整数の個数をdfsで求める。
(注意:桁あふれ)
■最大の素因数をdpする方法
その数字の最大の素因数を保持するint maxp[MAX_N+1]を用意し、0で初期化。maxp[1]=1;
i=2からスタートして、もしmaxp[i]==0の時は、maxp[i]=iとし、iの倍数のところはmaxp[i*j]=max(maxp[i*j], i)と計算していく。

反省

前者の方法でやったけれども、影響がないと思ってたmapで(意味のない)メモ化をしていたせいでTLEした。mapなくしたら通った。mapの(log探索)処理を毎回するので無視できないシビアなケースだった。