project euler 85

問題

h*wの長方形格子の中にi*jの長方形がいくつあるか考える。(1<=i<=h,1<=j<=w)
長方形の合計数が2000000に一番近い個数の時の面積を答える。

考え方

DP。

実際に試そうとすると時間がかかりすぎてしまう。
h*wの時の個数は、\sigma_{i=1}^{h} \sigma_{j=1}^{w} {i*j}とかけるので、
(h+1)*wの時の個数は、\sigma_{i=1}^{h} \sigma_{j=1}^{w} {i*j} + (h+1) * \sigma_{j=1}^{w}と漸化式でかける。
あとは2000000を少し超えるあたりまで探索すれば見つかる。