問題４ 解説

　この問題を解くための単純な方法はいわゆる「ふるい」(sieve) という手法である．入力された部屋の面積の最大値を Smax とする． まず，1 から Smax までの整数が部屋の面積としてありえるかどうかを示す配列 ExistXY[1..Smax] を {0, …, 0} に初期化する．ただし，0 はありえないことを示す． x, y を適当な範囲で変化させて ExistXY[2xy + x + y] = 1 という代入を実行する．ただし，1 はその面積の部屋がありえることを示す．この操作の終了後も ExistXY[S] が 0 となっている場合，面積 S の部屋はありえない．x≦y と仮定しても一般性を失わないことに注意して，このアルゴリズムをまとめると以下のようになる．
    ふるいのアルゴリズム
  1. begin
  2. 　for S = 1 to Smax do
  3. 　begin
  4. 　　ExistXY[S] = 0 ;
  5. 　end ;
  6. 　x = 1 ;
  7. 　while 2(x2+x)≦Smax do
  8. 　begin
  9. 　　y = x ;
  10. 　　while (2xy + x + y)≦Smax do
  11. 　　begin
  12. 　　　ExistXY[2xy + x + y] = 1 ;
  13. 　　　y = y + 1 ;
  14. 　　end ;
  15. 　　x = x + 1 ;
  16. 　end ;
  17. 　Exist[S] = 0 の面積 S を出力する ;
  18. end
　ふるいの方法は Smax が小さいときには有効なのだが，この問題のように Smax が大きくなると配列 ExistXY が定義できない．あるいは定義できても大きすぎて実行時間が長くなるので有効ではない． S = 2xy + x + y のとき S - x = 2xy + y = (2x + 1)y だから (S - x) mod (2x + 1) = 0 が成り立つ．ただし，a mod b は a を b で割ったときの余りを表す．よって，S が部屋の面積としてありえるかどうかかの判定のアルゴリズムは以下のようになる．
    面積の判定アルゴリズム
  1. begin
  2. 　x = 1 ;
  3. 　while 2(x2 + x)≦ Smax do
  4. 　begin
  5. 　　if ( (S - x) mod (2x + 1) ) = 0 then 「ありえる」と判定する ;
  6. 　end ;
  7. 　「ありえない」と判定する ;
  8. end