2013-03-21 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を少し超えるあたりまで探索すれば見つかる。