解説


実装が少し重たいです。

約数列挙


まず、長方形を作るという点から、横(または縦)の長さは の約数である必要があります。

そこで、あらかじめ約数を列挙しておきます。(約数を求めながらでもよいですが、実装が分かりにくくなります。)

約数はC++ならvectorに、Pythonならlistに入れておくとよいでしょう。

判定問題


さて、各約数ごとに黒く塗りつぶされた部分が木となるかを判定します。

以下、黒く塗りつぶされた部分は頂点として扱います。

木である条件としては、

  • 全ての頂点が連結であること
  • 閉路をもたない

ことがあります。

これは、DFSで で求めることができます。

具体的には、最初の頂点から連結成分の個数を数え、その個数が全体と一致していればよいです。

閉路を持つ場合は、移動候補で前の頂点以外に既に探索してある場合なので、そのような場合に個数を などで置き換えてしまうと場合分けが不要です。

(最終的に個数が全体の頂点数と異なるようにすればよいです)

計算量


計算量を見積もります。 約数列挙に、かかり、約数の個数もで抑えることができます。 実際には、 までの約数の個数で最大となるのは、高度合成数を考えると 程と小さいです。

(調べるべき頂点数は高々 個なので)

判定部分は、先述のように でできます。

よって、 でこの問題を解くことができました。

余談


別解としてUnionFindを用いても解けますね。

みなさんは作問者の意図は汲みましたか?

ここはSyntaxコンですよ